Untitled
unknown
java
3 years ago
2.2 kB
7
Indexable
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]; } }
Editor is loading...