Maximum Value Contiguous Subsequence

The goal is to find the maximum value contiguous subsequence in the given array in the most optimum way.

The problem becomes interesting only if the given array contains negative values else the result is sum of the entire array.

To solve the problem consider the following array

A[1.............i............j.............n]

To have the maximum sum for each location we can have

Sum[j] = { max( S[j-1] + A[j], A[j] ) }

Since for each element j we can have only two scenarios either to add it the current window or add a new window.

Code

int maxIncreasingSubsequence (int *a, int len) {
   
    int *s =new int [len];
    s[0] = a[0];
    for (int i = 1;i<len; i++) {
        s[i] = 0;
        s[i] = max (s[i-1] + a[i], a[i]);
    }
   
    return s[i-1];
}