linear solving of maximum subarray problem (dynamic programming)

maximum_subarray.js

// Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

// Example:

// Input: [-2,1,-3,4,-1,2,1,-5,4],
// Output: 6
// Explanation: [4,-1,2,1] has the largest sum = 6.
// Follow up:

// If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


const maxSubArray = (nums) => {
    if (nums.length === 1) {
        return nums[0];
    }
    
    let prevSum = nums[0];
    let max = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        prevSum = nums[i] + (prevSum <= 0 ? 0 : prevSum);
        max = prevSum > max ? prevSum : max;
    }
    
    return max;
    
};

//is this an optimal solution?
// this solution is O(n)