MCSS – Linear time complexity
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(n).
Solution
Dynamic programming technique can be used to solve this problem in linear time.
1. Let the array of integers be A[0..N-1]
2. Let the MCSS that ends at position (i) be B[i]
3. B[i] is either an extension of B[i-1] by adding A[i] or just A[i] only.
This means B[i] = max (B[i-1] + A[i], A[i]). Once the auxiliary array B is populated then MCSS is the maximum value stored in B
Code
Here is a sample C++ code to do that
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 |
//Includes #include <iostream> using namespace std; //Function prototype int MCSS (int [], int); //Main function void main() { //Sample array int A[] = {2, -4, 1, 2}; //Print MCSS cout << "MCSS = " << MCSS(A, 4) << endl; } //Function recieves the input array A and the number of elements int MCSS (int A[], int n) { //Auxiliary array. Size hardcoded to 10 int B[10]; //MCSS ending at position 0 is just the first element B[0] = A[0]; //Populate B for (int i = 1; i < n; i++) { //MCSS ending at position i is the max of //B[i-1] + A[i] and A[i] so B[i-1] > 0 is the //same as B[i-1] + A[i] > A[i] if (B[i-1] > 0) { B[i] = B[i-1] + A[i]; } else { B[i] = A[i]; } } //Find the max value in B int max = B[0]; for (int i = 0; i < n; i++) if (B[i] > max) max = B[i]; return max; } |