[leetcode/lintcode 題解] 算法面試真題詳解：撿蘋果

描述

Alice 和 Bob 在一個漂亮的果園裡面工作，果園裡面有N棵蘋果樹排成了一排，這些蘋果樹被标記成1 - N号。

Alice 計劃收集連續的K棵蘋果樹上面的所有蘋果，Bob計劃收集連續的L棵蘋果樹上面的所有蘋果。

Alice和Bob選擇的區間不可以重合，你需要傳回他們能夠最大收集的蘋果數量。

• N 是整數且在以下範圍内：[2，600]
• K 和 L 都是整數且在以下範圍内：[1，N-1]
• 數組A的每個元素都是以下範圍内的整數：[1，500]

線上評測位址：

領扣題庫官網

樣例1
示例 1:
輸入:
A = [6, 1, 4, 6, 3, 2, 7, 4]
K = 3
L = 2
輸出: 24
解釋：因為Alice 可以選擇3-5顆樹然後摘到4 + 6 + 3 = 13 個蘋果， Bob可以選擇7-8棵樹然後摘到7 + 4 = 11個蘋果，是以他們可以收集到13 + 11 = 24。           

樣例2
示例 2:
輸入:
A = [10, 19, 15]
K = 2
L = 2
輸出: -1
解釋：因為對于 Alice 和 Bob 不能選擇兩個互不重合的區間。           

解題思路

這題的重點在于如何快速地得到數組上一個區間内所有值的和，我們可以用字首和來解決。

prefixSum(i)代表數組的前i個數的和，我們可以通過一次周遊求出，prefixSum(i) = prefixSum(i - 1) + A(i)。

那麼rangeSum(l, r) = prefixSum(r) - prefixSum(l - 1)，就可以在O(1)時間内求出數組上的區間和。

代碼思路

1. 計算A數組的字首和數組prefixSum。
2. 計算字首中長度為K的子段和最大值，用prefixK記錄。
3. 計算字首中長度為L的子段和最大值，用prefixL記錄。
4. 計算字尾中長度為K的子段和最大值，用postfixK記錄。
5. 計算字尾中長度為L的子段和最大值，用postfixL記錄。
6. 由于選擇的兩個區間不可重複，是以枚舉分界點，分為兩種情況：

• 取prefixK[i] + postfixL[i + 1]。
• 取prefixL[i] + postfixK[i + 1]。

複雜度分析

設蘋果樹個數為N。

時間複雜度

• 線上性時間内計算字首和，前字尾最大值和結果，總時間複雜度為O(N)。

空間複雜度

• 一共需要5個額外的長為N的數組，空間複雜度為O(N)。

public class Solution {
    /**
     * @param A: a list of integer
     * @param K: a integer
     * @param L: a integer
     * @return: return the maximum number of apples that they can collect.
     */
    public int PickApples(int[] A, int K, int L) {
        int n = A.length;
        if (n < K + L) {
            return - 1;
        }
        int[] prefixSum = new int[n];
        //計算字首和
        prefixSum[0] = A[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = A[i] + prefixSum[i - 1];
        }
        
        // prefixK 代表前 i 個數中，長度為 K 的子區間和的最大值
        int[] prefixK = new int[n];
        int[] prefixL = new int[n];
        
        // postfixK 代表後面 [i, n - 1] 中，長度為 K 的子區間和的最大值
        int[] postfixK = new int[n];
        int[] postfixL = new int[n];
        
        // 計算字首值
        for (int i = 0; i < n; i++) {
            if (i == K - 1) {
                prefixK[i] = rangeSum(prefixSum, i - K + 1, i);
            }
            else if (i > K - 1) {
                prefixK[i] = Math.max(rangeSum(prefixSum, i - K + 1, i), prefixK[i - 1]);
            }
            if (i == L - 1) {
                prefixL[i] = rangeSum(prefixSum, i - L + 1, i);
            }
            else if (i > L - 1) {
                prefixL[i] = Math.max(rangeSum(prefixSum, i - L + 1, i), prefixL[i - 1]);
            }
        }
        
        // 計算字尾值
        for (int i = n - 1; i >= 0; i--) {
            if (i + K - 1 == n - 1) {
                postfixK[i] = rangeSum(prefixSum, i, i + K - 1);
            }
            else if (i + K - 1 < n - 1) {
                postfixK[i] = Math.max(rangeSum(prefixSum, i, i + K - 1), postfixK[i + 1]);
            }
            if (i + L - 1 == n - 1) {
                postfixL[i] = rangeSum(prefixSum, i, i + L - 1);
            }
            else if (i + L - 1 < n - 1) {
                postfixL[i] = Math.max(rangeSum(prefixSum, i, i + L - 1), postfixL[i + 1]);
            }
        }
        
        int result = 0;
        // 枚舉分界點，計算答案
        for (int i = 0; i < n - 1; i++) {
            result = Math.max(result, prefixK[i] + postfixL[i + 1]);
            result = Math.max(result, prefixL[i] + postfixK[i + 1]);
        }
        return result;
    }
    private int rangeSum(int[] prefixSum, int l, int r) {
        if (l == 0) {
            return prefixSum[r];
        }
        return prefixSum[r] - prefixSum[l - 1];
    }
}           

更多題解參考：

九章官網solution