0 dynamic programming leetcode918. Maximum sum of circular subarrays

918. The maximum sum of the ring subarray

describe

Given a length of n An array of circular integers nums , return nums Non empty of Subarray Maximum possible and .

Ring array It means that the end of the array will be connected with the beginning in a ring . Formally , nums[i] The next element of this is nums[(i + 1) % n] , nums[i] The previous element of is nums[(i - 1 + n) % n] .

Subarray Can only contain fixed buffers at most nums Once for each element in the . Formally , For subarrays nums[i], nums[i + 1], …, nums[j] , non-existent i <= k1, k2 <= j among k1 % n == k2 % n .

 Example  1：

 Input ：nums = [1,-2,3,-2]
 Output ：3
 explain ： From subarray  [3]  Get the maximum and  3
 Example  2：

 Input ：nums = [5,-3,5]
 Output ：10
 explain ： From subarray  [5,5]  Get the maximum and  5 + 5 = 10
 Example  3：

 Input ：nums = [3,-2,2,-3]
 Output ：3
 explain ： From subarray  [3]  and  [3,-2,2]  You can get the maximum and  3
 

 Tips ：

n == nums.length
1 <= n <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104​​​​​​​

 source ： Power button （LeetCode）
 link ：https://leetcode.cn/problems/maximum-sum-circular-subarray
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Compared with non ring arrays, there is a case of the largest sum of subarrays spliced together from beginning to end , Reverse this situation , That is, when the array sum is unchanged , Find the sum of the minimal array , Then the rest is the largest subarray and .
In addition, we should also consider the case that all numbers are negative , The smallest array is the largest number .

class Solution {
    
    public int maxSubarraySumCircular(int[] nums) {
    
int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = nums[0];
        int min = nums[0];
        int sum = nums[0];
        int maxest = nums[0];
        for (int i = 1; i < n; i++) {
    
            dp[i] = dp[i-1] < 0 ? nums[i] : nums[i] + dp[i-1];
            ans = Math.max(ans,dp[i]);
            sum += nums[i];
            maxest = Math.max(maxest,nums[i]);
        }
        Arrays.fill(dp,0);
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
    
            dp[i] = dp[i-1] > 0 ? nums[i] : nums[i] + dp[i-1];
            min = Math.min(min,dp[i]);
        }
        if (Math.max(ans,sum-min) != 0) {
    
            return Math.max(ans,sum-min);
        }
        return maxest;
    }
}