Problem: 53. 最大子数组和
思路
首先就是赋予dp[0]为nums[0],然后循环遍历数组判断dp[i-1]是否小于0，如果小于0那么dp[i]就是nums[i]，负责dp[i]就是dp[i-1]+nums[i],这样就可以保证每个dp[i]都是目前序列的最大值，最后返回最大的dp[i]就好
解题方法
描述你的解题方法
复杂度
- 时间复杂度:
添加时间复杂度, 示例： O ( n ) O(n) O(n)文章来源：https://www.toymoban.com/news/detail-450593.html
- 空间复杂度:
添加空间复杂度, 示例： O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-450593.html
优化前：code
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int res = dp[0] = nums[0];
for(int i = 1;i<n;i++){
if(dp[i-1]<0){
dp[i] = nums[i];
}else{
dp[i] = dp[i-1]+nums[i];
}
res = Math.max(res,dp[i]);
}
return res;
}
}
优化后：Code，直接在原来数组基础上改动
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int res = nums[0];
for(int i = 1;i<n;i++){
nums[i]+=nums[i-1]>=0?nums[i-1]:0;
res = Math.max(res,nums[i]);
}
return res;
}
}
到了这里，关于最大子数组和:动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
