推荐订阅源

Given one array, and calculate its maximum sum from any sequential subarray set
Cpp code demo as below:

 1 int maxSubarraySum(int arr[], int length, int& beg, int& end)
 2 {
 3     assert(arr!=0);
 4     int maxSum = 0;
 5     int tmpSum = 0;
 6     beg = 0; end = 0;
 7     for (int i = 0; i < length; i++) {
 8         tmpSum += arr[i];
 9         if (tmpSum < 0) {   // discard it
10             tmpSum = 0;
11             beg = end = i+1;
12         }
13         if (tmpSum > maxSum) {
14             maxSum = tmpSum;
15             end = i+1;
16         }
17     }
18     if (maxSum ==0 ) {      // if all numbers are negative, return max value
19         maxSum = arr[0];
20         for (int i = 1; i < length; i++)
21             if (maxSum < arr[i]) {
22                 maxSum = arr[i];
23                 beg = i; end = i+1;
24             }
25     }
26     return maxSum;
27 }
28