Finding the sum of the largest subsequence

Title: Find the maximum sum of the sublists of a list

Example:

    const arr = [8.- 19.5.4 -.20];
    // The largest subsequence [5, -4, 20], and is 21
Copy the code

Idea 1: When faced with this problem, the first thing that comes to mind is a double-layer loop to calculate all the possibilities and then calculate the result. This method is feasible, but the time complexity O(n^2) is obviously not a high quality algorithm

Idea 2: We introduce the concept of an increment, which we keep if it is beneficial to our result (gain greater than 0), and instead assign the current loop’s array item to this gain (the start of another subsequence).

Formula:

    dp = max(dp + current, current)
Copy the code

Leet Code has a nice picture of it

pic

In the code


const array = [8.- 19.5.4 -.20];

const getMaxChildList = function(array: number[]) :number {
    let maxSum = array[0];
    let maxContinuousSum = 0;
    for (let i = 0; i < array.length; i++) {
        if (maxContinuousSum > 0) {
            maxContinuousSum = maxContinuousSum + array[i];
        } else {
            maxContinuousSum = array[i];
        }
        maxSum = Math.max(maxContinuousSum, maxSum);
    }
    return maxSum;
};

Copy the code