Zero Lee的专栏

Calculate maximum sum of any subarray set

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 


posted on 2010-10-18 12:27 Zero Lee 阅读(252) 评论(0)  编辑 收藏 引用 所属分类: Data structure and algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理