Java数据结构与算法(最大子数组和动态规划)

前言

动态规划主要用于解决具有重叠子问题和最优子结构性质的问题。它通过将问题分解为子问题来解决复杂问题，每个子问题仅解决一次，并将其结果存储，以供后续使用，从而避免了重复计算。

对应leetcode. - 力扣（LeetCode）

实现原理

两次循环遍历，采用固定其实位置为i，不断滑动j的思想，来计算i，j区间内的最大值，略暴力。

初始化:dp[i][i]=nums[i];

转移方程：dp[i][j]=dp[i][j-1]+nums[j];

边界条件:无

具体代码实现

package test14;


class Solution {
    public int maxSubArray(int[] nums) {  
        int[][] dp=new int[nums.length][nums.length+1];
        int res=nums[0];
        for(int i=0;i<nums.length;i++){ 
            dp[i][i]=nums[i];
            res=Math.max(dp[i][i],res);
            for(int j=i+1;j<nums.length;j++){
                dp[i][j]=dp[i][j-1]+nums[j];
                res=Math.max(dp[i][j],res);
            }
        }
        return res;
        
    }
}

QA1:能否进行内存优化？

class Solution {
    public int maxSubArray(int[] nums) {  
        int res=nums[0];
        for(int i=0;i<nums.length;i++){ 
            int a=nums[i];
            res=Math.max(a,res);
            for(int j=i+1;j<nums.length;j++){
                int b=a+nums[j];
                res=Math.max(b,res);
                a=b;
            }
        }
        return res; 
    }
}

QA2:能否进行时间优化？

更新动态转移方程:pre<0时，pre=nums[i],pre不小于0时pre=nums[i]+pre;

核心是pre的计算，pre如果大于0，则持续与当前值num[i]相加，如果pre小于0，pre则为更新为num[i]。

class Solution {
    public int maxSubArray(int[] nums) {  
        int res=nums[0];
        int pre=0;
        for(int i=0;i<nums.length;i++){ 
            if(pre<0){
                pre=nums[i];
            }else{
                pre=nums[i]+pre;
            }
            res=Math.max(pre,res);
        }
        return res; 
    }
}