LeetCode 918. Maximum Sum Circular Subarray
2020-05-17 10:17:58 # leetcode # dynamic programming # array # leetcode

Problem

LeetCode 918. Maximum Sum Circular Subarray

1. 题目简述

给出一个环形数组A，找出其非空子序列的最大sum值。例如：

Example 1:
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

2. 算法思路

Greedy & Dynamic Programming

首先，这道题和LeetCode 53 Maximum Subarray 有异曲同工之妙，我们先来回忆一下如何求一个数组的子序列的最大值。

假设某数组arr长度为n，对于中间某位置第i个元素，设函数F(i)为元素0到i的包含元素i的最大子序列之和，则F(i+1)有如下推导：

$$F(i+1)=max(F(i)+arr[i+1],F(i))（0< i< n)$$

每次循环都记录F(i)和全局maxValue值的比较，循环结束，maxValue即为所求。

当我们确定了如何求最大值时，也就意味着我们如何求最小子序列值，与上同理。

对于一个环形序列来说，最大子序列有两种可能，一种是和普通的数组一样，并没有从数组的队尾绕回队首；第二种可能性是最大子序列从队尾绕回了队首。

对于前者来说，计算方法和53题一致，对于后者来说就有点麻烦了，如果还是用常规思路比较复杂。我们反过来想，如果一个数组和为sum，其最小子序列之和为minSubValue，那么它的环形最大子序列之和就是sum-minSubValue。

Corner Case

Attention：这里有一个很可怕的corner case，如果数组全部为负数（Example 5），那么其全局最小子序列值为所有值之和，环形最大子序列之和就为0，这种情况应当直接返回连续最大子序列之和，其实也就是整个数组的最大值，也是负数（但凡有一个正数都不会这样）。

3. 解法

  1. 注意使用变量记录当前界定个数，方便循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int contiguousMaxValue = contiguousMax(A);
        int cicularMaxValue = cicularMax(A);

        return contiguousMaxValue < 0 ? contiguousMaxValue : Math.max(contiguousMaxValue, cicularMaxValue);
    }

    private int contiguousMax (int[] A) {
        int maxValue = Integer.MIN_VALUE, currentMax = 0;

        for (int i = 0; i < A.length; i++) {
            currentMax += A[i];
            maxValue = currentMax > maxValue ? currentMax : maxValue;
            currentMax = currentMax < 0 ? 0 : currentMax;
        }

        return maxValue;
    }

    private int cicularMax (int[] A) {
        int minValue = Integer.MAX_VALUE, sum = 0, currentMin = 0;

        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            currentMin += A[i];
            minValue = currentMin < minValue ? currentMin : minValue;
            currentMin = currentMin > 0 ? 0 : currentMin;
        }

        return sum - minValue;
    }
}
2020-05-17 10:17:58 # leetcode # dynamic programming # array # leetcode
Next