本文主要是介绍最大子序和环形子数组最大和（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，动态规划）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！