应用题-动态规划-最大子数组和
- 版权声明：本站原创文章，于2026-06-02，由 管理员 发表。
- 转载请注明： 应用题-动态规划-最大子数组和 | CodeGarden
```python
class Solution:
# 一个整数数组nums，请找出一个具有最大和的连续子数组，返回其最大和。
# 子数组最少包含一个元素，子数组是数组中的一个连续部分。
# 1 <= nums.length <= 10e5
# -10e4 <= nums[i] <= 10e4
def maxSubArray(self, nums: List[int]) -> int:
n = len( nums )
if n == 1: return nums[ 0 ]
# dp[ i ]表示以nums[ i ]结尾的数组的最大子数组和 ( 数组范围 nums[ 0 ~ i] )
dp = [ nums[ i ] for i in range( n ) ]
ans = nums[ 0 ]
for i in range( 1, n ):
dp[ i ] = max( dp[ i - 1 ] + nums[ i ], nums[ i ] )
if dp[ i ] > ans: ans = dp[ i ]
return ans
```