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

Add a Comment

Your email address will not be published. Required fields are marked *