Maximum Subarray

Leetcode Problem 53: Maximum Subarray

Problem Summary

Given an integer array nums, find the contiguous subarray (containing at least one element) with the largest sum and return its sum.

Constraints:

• The array has between 1 and 100,000 elements.
• Each element is an integer in the range [-10,000, 10,000].

Techniques

• Array
• Divide and Conquer
• Dynamic Programming

Solution

function maxSubArray(nums: number[]): number {
    let maxSum = nums[0]
    let currentSum = nums[0]

    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i])
        maxSum = Math.max(maxSum, currentSum)
    }

    return maxSum
};

console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))