华为OD机试-2024年E卷-贪吃的猴子[200分]

样例输入 1

7
1 2 2 7 3 6 1  
3

样例输出 1

10

样例输入 2

3
1 2 3
3  

样例输出 2

6

样例输入 3

4
4 2 2 3
2

样例输出 3

7

思路：

1：bananaCounts 方法用的是暴力破解，好比说输入是

4

4 2 2 3

2

那我们求的时候可以从尾部开始取 2 3， 3 4， 4 2三个，代码实现就是，从a.length - n + i开始遍历计算count，i的范围是<采摘次数+1次。

2：贪心

public class OJTest5 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        int N = in.nextInt();
        System.out.println(bananaCounts(a, N));
        System.out.println(bananaCounts2(a, N));
    }

    private static int bananaCounts(int[] a, int n) {
        int maxCount = 0;
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int flag = 0;
            for (int j = a.length - n + i; j < a.length + i; ) {
                if (j >= a.length) {
                    j = j % a.length;
                }
                count += a[j];
                j++;
                flag++;
                if (flag == n) {
                    break;
                }
            }
            maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }
    private static int bananaCounts2(int[] a, int n) {
        int maxScore = 0;
        for (int i = 0; i < n; i++) {
            maxScore += a[i];
        }

        int currentScore = maxScore;
        int left = n - 1, right = a.length - 1;
        while (left >= 0) {
            maxScore -= a[left--];
            maxScore += a[right--];
            currentScore = Math.max(currentScore, maxScore);
        }
        return currentScore;
    }
}