# LeetCode: Maximum Subarray Solution

A classic DP problem

## 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))

## Brute-force

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}var maxSubArray = function (nums) {2  const n = nums.length3  let res = nums4
5  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  }12
13  return res14}```

## 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}```

Original problem

## Tags

leetcode

recursion

dynamic programming

## Next Post

Aug 24, 2021

Plus with remainder

## Previous Post

LeetCode: Length of Last Word

Aug 23, 2021

One-line KO

Search Posts