All files / leetCode 0053.ts

1
2
3
4
5
6
7
8
9
10
11
12
13
 
3x
 
3x
 
 
15x
15x
 
 
3x
 
 
export default function maxSubArray(nums: number[]): number {
  let dp = nums[0]
 
  for (let i = 0, sum = 0; i < nums.length; i++) {
    // DP formula: f(i) = Math.max(f(i−1) + nums[i], nums[i])
    // Solution : Max(f(i)), 0 <= i <= nums.length - 1;
    sum = Math.max(sum + nums[i], nums[i])
    dp = Math.max(dp, sum)
  }
 
  return dp
}