LeetCode: Maximum Subarray Solution

A classic DP problem

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

Comments

Loading comments...

Tags

leetcode

recursion

dynamic programming

Next Post

LeetCode: Add Binary

Plus with remainder

Previous Post

HoningJS

Search Posts