Data : -3, 4, 5, -2, -1, 2, 6, -4

c++

Finding the maximum subsequence

use two for loop

1 2 3 4 5 6 7 8 9 * Recursive maximum contiguous subsequence sum algorithm. * Finds maximum sum in subarray spanning a[left..right]. * Does not attempt to maintain actual best sequence. */ int maxSumRec( const vector int> & a, int left, int right) { if( left == right) // Base case if( a[ left ] > 0 ) return a left ]; else return 0; 10 11 12 13 14 15 16 17 int center = ( left + right ) / 2; int maxLeftSum = maxSumRec( a, left, center ); int maxRightSum = maxSumRec( a, center + 1, right); 18 19 20 21 int maxLeftBorderSum = 0, leftBorderSum = 0; for(int i = center; i >= left; --i) { leftBorderSum += a[i]; if( leftBorderSum > maxLeftBorderSum ) maxLeft BorderSum = left BorderSum; } 23 24 25 26 27 28 29 int maxRightBorderSum = 0, rightBorderSum = 0; for(int j = center + 1; j maxRightBorderSum ) maxRightBorderSum = rightBorderSum; } 30 31 32 33 34 return max3( maxLeftSum, maxRight Sum, maxLeftBorderSum + maxRightBorderSum ); 35 } 36 37 38 39 40 41 42 43 * Driver for divide-and-conquer maximum contiguous * subsequence sum algorithm. */ int maxSubSum3 ( const vector int> & a ) { return maxSumRec( a, 0, a.size() - 1); } 44 45