题解 | JZ42 连续子数组的最大和
这道题可以从标准的动态规划(DP)推过来。
我们可以假设dp[i]表示以位置i为结尾的子数组的最大和是多少？
所以对于我们要求的答案就是max(dp[0], dp[1], ..., dp[n])
在这n个数中找到一个最大值就是我们最后的答案。
而对于单独的dp[i]，我们可以递推得到：
dp[i] = max(dp[i-1] + nums[i], nums[i])
意思是当前位置的i可以接上一个的答案，也可以另起炉灶从当前统计答案。
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int ans = array[0];
int sum = array[0];
for (int i = 1; i < array.size(); i++) {
sum = max(sum+array[i], array[i]);
ans = max(ans, sum);
}
return ans;
}
};
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型
#
class Solution:
def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
# write code here
ans = array[0]
sumn = array[0]
for i in range(1, len(array)):
sumn = max(sumn+array[i], array[i])
ans = max(ans, sumn)
return ans
网易公司福利 162人发布
