The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A Subsequence

A subsequence is a sequence that can be derived from an array or another sequence, by removing zero or more elements, without changing the order of the remaining elements. The subsequence maintains the order it had in the original array or original sequence.

In general, for the original sequence of size n, there can be up to (2ⁿ - 1) non-empty sub-sequences in total.

For example, in the array [1, 2, 3, 4], there are 15 non-empty sub-sequences, which are:

[1], [2], [3], [4], [1,2], [1,3],[1,4], [2,3], [2,4], [3,4], [1,2,3], [1,2,4], [1,3,4], [2,3,4], [1,2,3,4] .

This is the number of combinations, but maintaining the order of appearance in the given (original) array.

A complete (power set) of subsequences of any array includes the empty subsequence: []. With that, the total number of possible subsequences from the original array is 2ⁿ .

Even-number only type subsequences from the 15 subsequences above, are:

[2], [4], [2,4]

which are not up to half of the 15 subsequences constituting the whole set (of subsequences).

Odd-number only type subsequences from the 15 subsequences above, are:

[1], [3], [1,3]

which are not up to half of the 15 subsequences constituting the whole set (of subsequences).

Out of the whole set of possible subsequences, only one or more subsequences with a characteristic description, is usually required.

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

A Sliding Window

A sliding window is a sub-array that moves from one end of the array to the other end, one element at a time. The left end of the window is typically identified by the variable, i or left or back. The right end of the window is typically identified by the variable, j or right or front.

As the window moves, its size (length) may be fixed or variable.

The sliding window is a specialized application of the two-pointers technique.

Problem

Given an array A[] of size N, the task is to find the maximum sum of a non-empty subsequence present in the given array.

Assume that the smallest negative number element is -1000.

Examples:

Input: A[] = { 2, 3, 7, 1, 9 }
Output: 22
Explanation:
Sum of the subsequence { A[0], A[1], A[2], A[3], A[4] } is equal to 22 (the whole array), which is the maximum possible sum of any subsequence of the given array.
Therefore, the required output here is 22.

Input: A[] = { -2, 11, -4, 2, -3, -10 }
Output: 13
Explanation:
Sum of the subsequence { A[1], A[3] } is equal to 13, which is the maximum possible sum of any subsequence of the given array. Therefore, the required output here is 13.

Brute Force (Naive) Approach

The simplest (naive) approach to solve this problem, is to generate all possible non-empty subsequences of the array, and calculate the sum of each subsequence of the array. Finally, print the maximum sum obtained from the subsequences.

Time Complexity for this brute force approach is O(N * 2^N)
Space complexity is typically more than O(N²)

Those are high values.

Efficient (Smart) Approach

Special Required Knowledge

- If all the numbers in the array are positive numbers, then the maximum sum is the sum of all the numbers.
- If some of the numbers in the array are positive and others are negative, then the maximum sum is the sum of only the positive numbers together.
- If all the numbers in the array are negative, then the maximum sum is the one biggest negative number. Note this: the sum of more than one negative number is smaller than any of the negative numbers.

In this scheme, an element number of 0 is a positive number.

Efficient Program in O(n) Time

The efficient program is (read through the code and comments):

#include <stdio.h>

int maxNonEmpSubSeq(int A[], int n) {
    int maxSumPos = 0;
    int maxSunNeg = -1000;
    
    for (int i = 0; i < n; i++) {
        //positive numbers
        if (A[i] > 0) {
            maxSumPos = maxSumPos + A[i];
        }
        
        //negative numbers only
        if (A[i] < 0) {
            if (A[i] > maxSunNeg)
                maxSunNeg = A[i];
        }
    }
    
    //finalizing
    int maxSum = maxSumPos;    //at this point, if there was at least one number greater than 0
    if (maxSumPos == 0)    //then maxSum is negative
        maxSum = maxSunNeg;
    
    return maxSum;
}

int main(int argc, char **argv) {
    int A1[] = {2, 3, 7, 1, 9};
    int n1 = sizeof(A1) / sizeof(A1[0]);
    int ret1 = maxNonEmpSubSeq(A1, n1);
    printf("%i\n", ret1);
    
    int A2[] = {-2, 11, -4, 2, -3, -10};
    int n2 = sizeof(A2) / sizeof(A2[0]);
    int ret2 = maxNonEmpSubSeq(A2, n2);
    printf("%i\n", ret2);
    
    int A3[] = {-6, -5, -4, -3, -2, -2, -7, -8, -9};
    int n3 = sizeof(A3) / sizeof(A3[0]);
    int ret3 = maxNonEmpSubSeq(A3, n3);
    printf("%i\n", ret3);
    
    return 0;
}

The output is:

    22
    13
    -2

The time complexity is O(n), where n is the length of the array. The space complexity is O(n), where n is the length of the same array in the calling function and called function. Any extra time or extra space used is ignored, in quoting the time or space complexity.

Thanks for reading.