CC150 17.8

17_8.cpp

/* CC150 17.8 */
// find the contiguous sequence with the largest sum, return the sum
// book solution

#include <iostream>
#include <vector>

using namespace std;

// what if required to return start and end indices of the sequence?!!
int maxSum(vector<int> arr)
{
	// no need to shrink the array! doesn't affect the algorithm
	int sum = 0, maxSum = 0;
	for (auto begin = arr.cbegin(); begin != arr.cend(); ++begin) {
		sum += *begin;
		if (sum < 0) // disgard previous sequence and reset sum
			sum = 0;
		else { // still addable, keep searching
			if (sum > maxSum)
				maxSum = sum;
		}
	}
	return maxSum; // return 0 if the whole array is negative
}

int main()
{
	vector<int> arr;
	int data;
	while (cin >> data)
		arr.push_back(data);
	cout << maxSum(arr) << endl;
	return 0;
}