^{2}), which although polynomial, is time expensive.

There is a O(n) solution: go through each index of the array, remembering what the max sum is until now, from where it starts and where it ends. At each step, remember a local sub-array and check if it's larger than the maximum. If it is, the maximum becomes the current sub-array. If the local sum ever becomes <0, just restart the sub-array with the next index. Here's the algorithm:

1: int arr[10] = {3, 1, 6, -1, -7, 3, 10, -5, 0, 1};

2: int maxsum = arr[0];

3: int maxstart = 0;

4: int maxend = 0;

5: int sum = arr[0];

6: int start = 0;

7: for (int i = 1; i < 10; i++) {

` 8: sum += arr[i];`

9: if (sum > maxsum) {

` 10: maxsum = sum;`

` 11: maxend = i;`

` 12: maxstart = start;`

` 13: }`

14: if (sum < 0) {

` 15: sum = 0;`

` 16: start = i + 1;`

` 17: }`

` 18: }`

19: cout << "maxsum=" << maxsum << endl;

20: cout << "sequence: ";

21: for (int i = maxstart; i <= maxend; i++) {

22: cout << arr[i] << " ";

` 23: }`

` 24: cout << endl;`

Here's what this prints:

` 1: maxsum=15`

` 2: sequence: 3 1 6 -1 -7 3 10`

## No comments:

## Post a Comment