Cumulative Sum Approach
| 26 | |
| 27 | //Cumulative Sum Approach |
| 28 | int maxSubArraySum2(int a[],int n) |
| 29 | { |
| 30 | const int N= n+1; |
| 31 | int currsum[N]; |
| 32 | currsum[0] = 0; |
| 33 | int maxSum = INT_MIN; |
| 34 | |
| 35 | for(int i=1;i<=n;i++) |
| 36 | { |
| 37 | currsum[i] = currsum[i-1] + a[i-1]; |
| 38 | } |
| 39 | |
| 40 | for(int i=1;i<=n;i++) |
| 41 | { |
| 42 | int sum=0; |
| 43 | for(int j=0;j<i;j++) |
| 44 | { |
| 45 | sum = currsum[i] - currsum[j]; |
| 46 | maxSum = max(sum,maxSum); |
| 47 | } |
| 48 | } |
| 49 | return maxSum; |
| 50 | } |
| 51 | |
| 52 | |
| 53 | //kadene's algorithm |