Java教程

环形最大子数组和

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

环形最大子数组和

题目来源:leetcode第918题。环形最大子数组和

题目

给定一个由整数数组 \(A\) 表示的环形数组 \(C\),求 \(C\) 的非空子数组的最大可能和。在此处,环形数组意味着数组的末端将会与开头相连呈环状。(形式上,当 \(0 <= i < A.length\) 时 \(C[i] = A[i]\),且当 \(i >= 0\) 时 \(C[i+A.length] = C[i]\)。此外,子数组最多只能包含固定缓冲区 \(A\) 中的每个元素一次。(形式上,对于子数组 \(C[i], C[i+1], ..., C[j]\) ,不存在 \(i <= k1, k2 <= j\) 其中 \(k1 % A.length = k2 % A.length\) )

解决方法

该方法来自这里,他的方法通俗易懂。

简单来说,要求该环行数组的最大和,分成两种情况:

  1. 最大子数组和不成环,所以问题就转换成了在普通数组中求最大子数组和的问题。(leetcode第53题)
  2. 最大子数组成环。即最大子数组两个子序列在原数组的两边。则我们可以把问题进行转化一下。最大子数组和 = 数组总和 - 最小子数组和(最大和子数组与最小和子数组是相互互斥的,因为最大和子数组成环,所以最小和子数组必不成环)。则就变成了求普通数组中最小和子数组。
    所以,问题就转换成以上两种情况中的最大值。

该解法涉及到一种情况是:

  • 当数组每个元素都小于0时,按照上面解法求出来的结果是0,但是数组每个元素都小于0,与题意相矛盾,所以我们还要判断当第一种情况小于0时,answer 为数组中最大值元素。

c++代码

class Solution{
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int ans;
        int n = nums.size();
        int sum = 0;
        int dmin = 30000 + 1;
        int dmax = -30000 - 1;
        vector<int> dpmax(n + 1,0);
        vector<int> dpmin(n + 1,0);
        for(int i = 1;i <= n;i++){
            dpmax[i] = max(dpmax[i - 1] + nums[i - 1],nums[i - 1]);
            dpmin[i] = min(dpmin[i - 1] + nums[i - 1],nums[i - 1]);
            dmax = dmax>dpmax[i]?dmax:dpmax[i];
            dmin = dmin<dpmin[i]?dmin:dpmin[i];
            sum += nums[i - 1];
        }
        if(dmax >= 0) ans = max(dmax , sum - dmin);
        else ans = dmax;
        return ans;
    }
};
这篇关于环形最大子数组和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!