最大子数组蛮力法对第一个数组产生大和

Question

我想不出哪里出了问题。任何帮助都将不胜感激！

下面是运行算法并将其打印到输出文件的函数：

void a1(int a[], int size, string filename){ 

//run algorithm 1
int sum = a[0], start = 0, end = 0;
for (int x = 0; x < size; x++) {
    int tempSum = 0;
    int y = x;
    while(y>=0){
        tempSum += a[y];
        if(tempSum>sum){
            sum=tempSum;
            start=y;
            end=x;
        }
        y--;
    }
}

//print results on file
ofstream output;
output.open(filename.c_str(), ios::out | ios::app);
output << "\nMax sum array: ";
    for (int x = start; x <= end; x++) {
        output << a[x];
        if (x != end) output << ", ";
    }
output << "\nMax sum value: " <<  sum << "\n";
output.close();
} 

以下是主文件：

int main() {
    int a[50];
    ifstream inputFile;
    string s;
    stringstream ss;
    string outputfile = "MSS_Results.txt";

//print title
ofstream output;
output.open(outputfile.c_str(), ios::out | ios::app);
output << "Algorithm 1:\n";
output.close();

//read file and run a1
int size;
char c;
inputFile.open("MSS_Problems.txt");
while (!inputFile.eof()) {
    getline(inputFile, s);
    size = 0;
    ss << s;
    ss >> c;
    while (ss.rdbuf()->in_avail()) {
        ss >> a[size];
        size++;
        ss >> c;
        if (!ss.rdbuf()->in_avail() && c != ']') {
            ss.clear(); 
            getline(inputFile, s);
            ss << s;
        }
    }
    ss.clear();
    if (size > 0) a1(a, size, outputfile);
}
inputFile.close();

  return 0;
}

[1, 2, 4, -1, 4, -10, 4, -19, 18, -1, -3, -4, 11, 3, -20, 19, -33, 50, 66, -22, -4, -55, 91, 100, -102, 9, 10, 19, -10, 10, 11, 11, -10, -18, 50, 90]
[12, 12, 14, -88, -1, 45, 6, 8, -33, 2, 8, -9, -33, -8, -23, -77, -89, 1, 9, 10, 92, 87]
[565, 78, 33, 9, 10, 84, 71, -4, -22, -55, -10, 76, -9, -9, -11, 76, 89, 11, 10, -33, 9]
[2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

Algorithm 1:

Max sum array: 50, 66, -22, -4, -55, 91, 100, -102, 9, 10, 19, -10, 10, 11, 11, -10, -18, 50, 90, 3897136
Max sum value: 3897432

Max sum array: 1, 9, 10, 92, 87, 91
Max sum value: 290

Max sum array: 565, 78, 33, 9, 10, 84, 71, -4, -22, -55, -10, 76, -9, -9, -11, 76, 89, 11, 10, -33, 9, 87
Max sum value: 1055

Max sum array: 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 11
Max sum value: 103

[12, 12, 14, -88, -1, 45, 6, 8, -33, 2, 8, -9, -33, -8, -23, -77, -89, 1, 9, 10, 92, 87]
[565, 78, 33, 9, 10, 84, 71, -4, -22, -55, -10, 76, -9, -9, -11, 76, 89, 11, 10, -33, 9]
[2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]

Algorithm 1:

Max sum array: 1, 9, 10, 92, 87, 624
Max sum value: 823

Max sum array: 565, 78, 33, 9, 10, 84, 71, -4, -22, -55, -10, 76, -9, -9, -11, 76, 89, 11, 10, -33, 9, 87
Max sum value: 1055

Max sum array: 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
Max sum value: 92

Answer 1

我错误地初始化了数组，这就是为什么它有时会在最后给我一个垃圾号。为了正确初始化，我只需更改

a[100];

到

a[100] = {0}

这就解决了数组末尾异常大数的问题。