Untitled

mail@pastecode.io avatar
unknown
java
2 years ago
2.2 kB
4
Indexable
Never
public class Apple {
 
    public static void main(String args[]) {
 
        int[] A = new int[]{ 6,1,4,6,3,2,7,4 };
 
        System.out.println(getMaxApples(A, 3, 2));
    }
 
    public static int getMaxApples(int[] A, int K, int L) {
        int n = A.length;
 
        if (n < K + L) {
            return -1;
        }
        
        int[] preSum = new int[n];
        preSum[0] = A[0];
        
        for (int i = 1; i < n; i++) {
            preSum[i] = A[i] + preSum[i - 1];
        }
 
        int[] prefixK = new int[n];
        int[] prefixL = new int[n];
        int[] postfixK = new int[n];
        int[] postfixL = new int[n];
 
        for (int i = 0; i < n; i++) {
            if (i == K - 1) {
                prefixK[i] = rangeSum(preSum, i - K + 1, i);
            }
            else if (i > K - 1) {
                prefixK[i] = Math.max(rangeSum(preSum, i - K + 1, i), prefixK[i - 1]);
            }
            if (i == L - 1) {
                prefixL[i] = rangeSum(preSum, i - L + 1, i);
            }
            else if (i > L - 1) {
                prefixL[i] = Math.max(rangeSum(preSum, i - L + 1, i), prefixL[i - 1]);
            }
        }
 
        for (int i = n - 1; i >= 0; i--) {
            if (i + K - 1 == n - 1) {
                postfixK[i] = rangeSum(preSum, i, i + K - 1);
            }
            else if (i + K - 1 < n - 1) {
                postfixK[i] = Math.max(rangeSum(preSum, i, i + K - 1), postfixK[i + 1]);
            }
            if (i + L - 1 == n - 1) {
                postfixL[i] = rangeSum(preSum, i, i + L - 1);
            }
            else if (i + L - 1 < n - 1) {
                postfixL[i] = Math.max(rangeSum(preSum, 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 static int rangeSum(int[] preSum, int l, int r) {
        if (l == 0) {
            return preSum[r];
        }
        return preSum[r] - preSum[l - 1];
    }
 
}