search

halfrost / LeetCode-Go

✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% / LeetCode 题解
https://books.halfrost.com/leetcode
MIT License
32.76k stars 5.68k forks source link

53. dp[i]定义有疑问 #174

Closed voidweapon closed 2 years ago

voidweapon commented 2 years ago

dp[i]表示[0, i]区间内各子区间和的最大值

对于输入 nums = [-2,1,-3,4,-1,2,1,-5,4] dp[0] = -2; dp[1] = 1; dp[2] = -3; // 但是[0,2]内子区间和的最大值应该是1，所以反证定义了。

状态转移是对的但是，dp[i]很难表述是什么

halfrost commented 2 years ago

@voidweapon 可以表示成，dp[i] 是以 i 为右区间的子区间的区间和的最大值。

voidweapon commented 2 years ago

配着wiki上这张图顿时就理解了 Maximum_Subarray_Visualization