LeetCode: Maximum Subarray Solution

Approach

Brute-force

Straight forward, 2 nested loop, accumulated sum and recalculate max

Dynamic programming

Let f(i) be the maximum sum of subarray ending with nums[i]

Base case: i === 0 then f(i) = nums[i]

Normal case for the rest of i: f(i) = max(nums[i], nums[i] + f(i-1))

The final result with be max(f(0), ..., f(i))

Implementation

Brute-force

1var maxSubArray = function (nums) {
2  const n = nums.length
3  let res = nums[0]
4
5  for (let i = 0; i < n; i++) {
6    let sum = 0
7    for (let j = i; j < n; j++) {
8      sum += nums[j]
9      res = Math.max(res, sum)
10    }
11  }
12
13  return res
14}

Memoized recursion

1var maxSubArray = function (nums) {
2  const memo = Array(nums.length).fill(null)
3
4  const recursion = i => {
5    if (i === 0) return nums[i]
6
7    if (memo[i] !== null) return memo[i]
8
9    const res = Math.max(nums[i], recursion(i - 1) + nums[i])
10
11    return (memo[i] = res)
12  }
13
14  return Math.max.apply(
15    null,
16    nums.map((_, i) => recursion(i))
17  )
18}

References

Original problem