算法学习 day26
第二十六天
最大子数组和
53. 最大子数组和 - 力扣（LeetCode）
动态规划问题
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
dp[0] = nums[0];
int res = dp[0];
for(int i = 1; i < len; i++){
dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
res = Math.max(dp[i],res);
}
return res;
}
}
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n,INT_MIN);
dp[0] = nums[0];
int ans = dp[0];
for(int i = 1;i < n;i++){
dp[i] = max(dp[i - 1]+ nums[i],nums[i]);
ans = max(dp[i],ans);
}
return ans;
}
};
