给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路分析
以 nums[i] 为结尾的「最大子数组和」为 dp[i]。
dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组
Python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
#base case
#第一个元素前面没有子数组
dp = [0]*n
dp[0] = nums[0]
#状态转移方程
for i in range(1,n):
dp[i] = max(nums[i], nums[i]+dp[i-1])
#得到 nums 的最大子数组
res = -10000
for i in range(0,n):
res = max(res,dp[i])
return res
C
int maxSubArray(int* nums, int numsSize){
if(numsSize==0)
return 0;
int sumCur=nums[0];//记录当前连续子序列的Max
int sumMax=nums[0];//记录全部连续子序列的Max
for(int i=1;i<numsSize;i++){
if(sumCur>0)
sumCur+=nums[i];
else
sumCur=nums[i];
if(sumCur>sumMax)
sumMax=sumCur;
}
return sumMax;
}
C++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
if(len == 0)
return 0;
int ans = nums[0], temp = nums[0];
for(int i = 1; i < len; i++) {
if(temp > 0) {
temp = temp + nums[i];
} else {
temp = nums[i];
}
ans = max(ans, temp);
}
return ans;
}
};
