Suppose that lines 15 and 16 are replaced by (LINE15) int maxLeftSum = maxSumRec( a, left, center - 1 ); and (LINE16) int maxRightSum = maxSumRec( a, center, right );

Would the routine still work?

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