您现在的位置是:首页 >其他 >最大子数组和:动态规划网站首页其他
最大子数组和:动态规划
简介最大子数组和:动态规划
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)
- 空间复杂度:
添加空间复杂度, 示例: O ( n ) O(n) O(n)
优化前: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;
}
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。