您的位置: 首页  >  IT文章  >  53最大子序和 题目（连续的，区别于不连续的子序列） 动态规划

53最大子序和 题目（连续的，区别于不连续的子序列） 动态规划

分类: IT文章 • 2022-07-23 21:59:32

https://leetcode-cn.com/problems/maximum-subarray/

动态规划

动态规划1（空间复杂度高）

使用二维数组

  1 2 3
1 1 3 6
2 0 2 5
3 0 0 3

1.　　初始化对角线

2.　　计算距离为2的和

3.　　计算距离为3的和

。。。

计算出右上角的值

程序：

    public int maxSubArray(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int len = nums.length;
        int[][] dp = new int[len][len];
        int max = Integer.MIN_VALUE;
        for(int i = 0 ;i < len ; i ++){
            dp[i][i] = nums[i];
            max = max > nums[i] ? max : nums[i];
        }

        for(int i = 1 ; i < len ; i++){
            for(int j = 0 ; i + j < len ; j ++){
                dp[j][i+j] = nums[j] + nums[i+j] + dp[j + 1][i + j -1];
                max = max > dp[j][i+j] ? max : dp[j][i+j];
            }
        }
        return max;
    }

动态规划2(最佳解决）

dp[i] = max( dp[i - 1] + nums[i] , nums[i])

 public int maxSubArray(int[] nums) {
        if(nums == null && nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];

        for(int i = 1 ; i < nums.length ; i ++){
            int temp = nums[i] + dp[i-1];
            if (temp > nums[i]){
                dp[i] = temp;
            }else{
                dp[i] = nums[i];
            }
            max = Math.max(dp[i],max);
        }
        return max;
    }

相关推荐