您现在的位置是:首页 >其他 >最大子数组和:动态规划网站首页其他

最大子数组和:动态规划

water-之 2024-06-17 11:19:03
简介最大子数组和:动态规划

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;

    }
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。