LeetCode: Maximum Subarray Solution
A classic DP problemApproach
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.length3 let res = nums[0]45 for (let i = 0; i < n; i++) {6 let sum = 07 for (let j = i; j < n; j++) {8 sum += nums[j]9 res = Math.max(res, sum)10 }11 }1213 return res14}
Memoized recursion
1var maxSubArray = function (nums) {2 const memo = Array(nums.length).fill(null)34 const recursion = i => {5 if (i === 0) return nums[i]67 if (memo[i] !== null) return memo[i]89 const res = Math.max(nums[i], recursion(i - 1) + nums[i])1011 return (memo[i] = res)12 }1314 return Math.max.apply(15 null,16 nums.map((_, i) => recursion(i))17 )18}
References
Comments
Loading comments...
Tags
leetcode
recursion
dynamic programming
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.