最大子序和环形子数组最大和(Java,动态规划)

2021/10/6 11:11:00

本文主要是介绍最大子序和环形子数组最大和(Java,动态规划),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

最大子序和

https://leetcode-cn.com/problems/maximum-subarray/
在这里插入图片描述

思路:
使用动态规划思想,在这里我使用一个temp表示当前的和,max表示最大值
在这里插入图片描述

代码如下:

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

环形子数组最大和

环形和普通的子数组最大和其实思路相似,我们的思路为:
分为两种情况
1.最大值为常规的子序列和不包括环 eg:-1 -2 3 -4
2.包括环 eg:[5,-4,5] 此时可用数组总和-连续的最小子序列和(不成环) 即为最大子序和。
有一种情况:当数组中全为负数 ,两个相减为0 ,这时候我们选择数组中最大的数。

 选择这两种情况中的最大值,即为我们需要求的。
if(nums.length==0)return 0;
    if(nums.length==1)return nums[0];
    int atemp=nums[0];
    int itemp=nums[0];
    int maxSum=nums[0];
    int minSum=nums[0];
    int sum=nums[0];
        for (int i = 1; i < nums.length; i++) {
            atemp=Math.max(atemp+nums[i],nums[i]);
            itemp=Math.min(itemp+nums[i],nums[i]);
            if(maxSum<atemp){
                maxSum=atemp;
            }
            if(minSum>itemp){
                minSum=itemp;
            }
            sum+=nums[i];
        }
        //说明数组中全为负数  返回最小的一个数
        int s=0;
        if(sum-minSum==0){
            Arrays.sort(nums);
            s=nums[nums.length-1];
        }
        return Math.max(maxSum,sum-minSum==0?s:sum-minSum);


这篇关于最大子序和环形子数组最大和(Java,动态规划)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程