Maximum Subarray Sum
ARRAY
DYNAMIC PROGRAMMING

Problem

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

Examples

maxSubArray([1, -2, 5, -4, 5]); // returns 6 // The maximum sum can be found in the subarray [5, -4, 5] // 5 + (-4) + 5 = 6 maxSubArray([-10,-5,-6,-8,-1]) // returns -1 // The least negative number forms the subarray with maximum sum.

Time Complexity

Can you figure out the O(n) solution?

Loading...