leetcode动态规划经典例题——53.最大子数组和

53.最大子数组和

 

题目描述：

思路：最大子数组和，要求我们找出一个具有最大和的连续数组，显而易见就是一道动态规划题，我们先找出dp[i]的规律；

题目要求具有最大和连续数组，重点在于连续，就意味着我们dp[i]的值是不是和dp[i-1](前一个位置的连续最大和)息息相关：

• 当dp[i-1]>=0时，dp[i] = dp[i-1] + nums[i]，
• 当dp[i-1]<0时，dp[i] = nums[i]

有了这个思路，我们写代码就很简单了：

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int max = nums[0];
        dp[0] = nums[0];
        for(int i = 1;i < nums.length;i++){          
            dp[i] = dp[i-1] >=0 ? dp[i-1] + nums[i] : nums[i];           
            max = Math.max(max,dp[i]);
        }
        return max;
    }

此时空间复杂度O(n)，但是不知道小伙伴们有没有发现，我们的dp[i]只用了一次，我们却创建了一整个dp数组，是不是很浪费空间，所以我们可以进行一个优化，用一个temp变量来代替dp数组

请看代码：

    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int temp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            temp = temp > 0 ? nums[i] + temp : nums[i];
            max = Math.max(max,temp);
        }
        return max;
    }

优化后空间复杂度O(1)，而且还缩短了进入dp数组的匹配值的时间，大大提高效率！