CODEWITHSUNDEEP
c++arrays
Arunav MAHESHWARI
Arunav MAHESHWARI

Reputation: 134

Maximum Sub-Array Sum C++

Given an array, I am trying to find the maximum sub-array sum. A sub-array is as follows. For example, I get the following array: [9, -7, 5, 3, 91]. Whilst [9, -7, 5] is a sub-array, [9, 5, 3, 91] is not. My code is below:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int arraylen, subarraylen, subarraysum, itervar1, itervar2, itervar3, incrementvar;
    cin >> arraylen;
    vector<int> mainarray(arraylen);
    vector<int> sumarray(arraylen * (arraylen-1) + 1);
    for (itervar1 = 0; itervar1 < arraylen; itervar1++) {
        cin >> mainarray[itervar1];
    }
    sumarray[0] = 0;
    for (itervar1 = 0; itervar1 < arraylen; itervar1++) {
        for (itervar2 = arraylen; itervar2 > 0; itervar2--) {
            subarraylen = itervar2-itervar1;
            if (subarraylen < 1) {
                continue;
            }
            vector<int> subarray(subarraylen);
            incrementvar = 0;
            for (itervar3 = itervar1; itervar3 < itervar2; itervar3++) {
                subarray[incrementvar] = mainarray[itervar3];
                incrementvar++;
            }
            subarraysum = 0;
            for (itervar3 = 0; itervar3 < subarraylen; itervar3++) {
                subarraysum += subarray[itervar3];
            }
        }
    }
    return 0;
}

For some reason, it doesn't work; just infinitely loops around. Any help would be appreciated.

Upvotes: 1

Views: 599

Answers (1)

Barmak Shemirani
Barmak Shemirani

Reputation: 31599

First, here is a routine to list all the sub arrays:

vector<int> vec{ 9, -7, 5, 3, 91 };
int sz = vec.size();
for(int start = 0; start < sz; start++)
{
    for(int end = start; end < sz; end++)
    {
        for(int j = start; j <= end; j++)
        {
            cout << vec[j] << ", ";
        }
        cout << "\n";
    }
}

Now you just have to get the total in loop j, add to a vector sum. You don't need to know the size of sum before hand. Use push_back to add total to sum.

Note, the array itself is included as a sub array, you can exclude that array depending on what the definition is.

Upvotes: 2

Related Questions