Contiguous Sequence

16.17 Contiguous Sequence: You are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the sum.

EXAMPLE
Input 2, -8, 3, -2, 4, -10
Output 5 (i.e., {3, -2, 4})

• Brute Force:

  • Find all n^2 solutions with their sums accumulated, and then find the largest sum. O(N^2).

• Best:

  • Something we can do for ourselves is manage when there is an improvement in the sequence, and when there is not. For example, if we begin with -2 as a number, then immediately, we know that (if there is any positive number out there), then we can just start from there. Therefore, we can ignore -2 in its entirity. This follows the idea that when our sum is negative, there is no room for improvement. For example, is the sequence {3,-2, 4}, 3 does decrease down to 1, but what this also means is that we are starting off with an additional positive number that could potentially increase, if we hadnt otherwise had it. In the same way, if we know that our sum is negative, then it could only mean its holding us back.

int max_cont_sum(vector<int> &nums) {
    if (nums.empty()) return 0;
    int sum, cur_max_potential, actual_max;
    sum = 0;
    cur_max_potential = actual_max = nums.at(0);

    for (auto &i : nums) {
        sum += i;
        if (sum < 0) {
            sum = 0;
        }
        else {
            cur_max_potential = sum;
        }
        if (cur_max_potential > actual_max) {
            actual_max = cur_max_potential;
        }
    }

    return actual_max;
}


int main() {
    vector<int> nums = { 2, -8, 3, -2, 4, -10 };
    cout << max_cont_sum({ nums }) << endl;

    nums = { 2 ,3, -8, -1, 2, 4, -2, 3 };
    cout << max_cont_sum({ nums }) << endl;

    nums = { -10,-100,3,4,-6,-5,10 };
    cout << max_cont_sum({ nums }) << endl;

    nums = { -10,-100,3,4,-6,-5 };
    cout << max_cont_sum({ nums }) << endl;

    nums = { 1,-100,3,4,-6,-1, 2 };
    cout << max_cont_sum({ nums }) << endl;
}