Maximum contiguous subsequence sum C++
Maximum contiguous subsequence sum problem
Given an array of N integers. The array is expected to contain positive as well as negative numbers. Find the maximum contiguous subsequence sum (MCSS) of the array. For example the MCSS of {2, -4, 1, 2} is 3 which is the sum of the subsequence {1, 2}. A brute force approach requires 3 nested loops with time complexity of O(N3). Write code to solve this problem with time complexity of O(nlogn). Hint: use divide and concur technique.
Maximum contiguous subsequence sum algorithm
finding maximum contiguous subsequence sum: split the array into two halfs. Note that one of the following three cases must hold:
1. The max subsequence is in the left half.
2. The max subsequence is in the right half.
3. The max subsequence begins in the left half and ends in the right half.
Once the above values are computed just take the maximum of the three values as the MCSS. The base case of the recursion is when we have only one element. In that case the LCSS is the element itself if it is positive otherwise the LCSS is 0. The tricky part is computing the LCSS in the third case. This is done by finding the maximum sum to the left of the center and the maximum sum to the right of the center then adding both values together.
Code
Here is the maximum contiguous subsequence sum in C++ code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
//Includes #include <iostream> using namespace std; //Function prototype int MCSS (int [], int, int); //Main function void main() { //Sample array int A[] = {2, -4, 1, 2}; //Print MCSS cout << "MCSS = " << MCSS(A, 0, 3) << endl; } //Function: takes as input the integer array, left and right //indices which are going to vary during recursive calls to //the function int MCSS (int A[], int left, int right) { //When left is equal to right then it means //a single element array in that case return //the element itself if it is positive otherwise //return zero if (left == right) { return A[left] > 0 ? A[left] : 0; } //Find the center element of the array int center = (left + right) / 2; //Call the function on the left half int maxLeftSum = MCSS(A, left, center); //Call the function on the right half int maxRightSum = MCSS(A, center + 1, right); //Holds the max sum to the left of the center int maxLeftCenterSum = 0; //Holds the max sum to the right of the center int maxRightCenterSum = 0; //Current sum as we move from center to the left int leftCenterSum = 0; //Current sum as we move from the center to the right int rightCenterSum = 0; //Find the max sum to the left of the center for (int i = center; i >= left; i--) { leftCenterSum += A[i]; if (leftCenterSum > maxLeftCenterSum) { maxLeftCenterSum = leftCenterSum; } } //Find the max to the right of the center for (int i = center + 1; i <= right; i++) { rightCenterSum += A[i]; if (rightCenterSum > maxRightCenterSum) { maxRightCenterSum = rightCenterSum; } } //MCSS is the max of the three computed values int max = maxLeftSum; if (maxRightSum > max ) { max = maxRightSum; } if (maxLeftCenterSum + maxRightCenterSum > max) { max = maxLeftCenterSum + maxRightCenterSum; } return max; } |
Please use the comments section below for questions, corrections or feedback. Thanks for reading.
About Author
Mohammed Abualrob
Software Engineer @ Cisco