How to find the sub-array with the maximum sum

Suppose you have an array of integers, and you want to find the sub-array with the maximum sum. One obvious solution would be to take each index, go through the rest of the numbers, find the local sub-array with the maximum sum and compare with the global found. But that would mean O(n²), 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