[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