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