题目描述

一只贪吃的猴子，来到一个果园，发现许多串香蕉排成一行，每串香蕉上有若干根香蕉。每串香蕉的根数由数组numbers给出。

猴子获取香蕉，每次都只能从行的开头或者末尾获取，并且只能获取N次，求猴子最多能获取多少根香蕉。

输入描述

第一行为数组numbers的长度

第二行为数组numbers的值每个数字通过空格分开

第三行输入为N，表示获取的次数

输出描述

按照题目要求能获取的最大数值

备注

• 1 ≤ numbers.length ≤ 100000
• 1 ≤ numbers ≤ 100
• 1 ≤ N ≤ numbers.length

用例1

输入

7
1 2 2 7 3 6 1
3

Copy

输出

10

Copy

说明

第一次获取香蕉，无论是从行的开头或者末尾获取，得到的香蕉根数目为1, 但是，从行末尾获取能获取到最优的策略，后面可以直接得到香蕉根数目6和3。因此最终根数为1+6+3=10

用例2

输入

3
1 2 3
3

Copy

输出

6

Copy

说明

全部获取所有的香蕉，因此最终根数为1+2+3=6

用例3

输入

4
4 2 2 3
2

Copy

输出

7

Copy

说明

第一次获取香蕉为行的开头，第二次获取为行的末尾，因此最终根数为4+3=7

乍一看，这个题目和前面【dfs && 记忆化搜索】OD374. 分披萨 很相似，前一题是2个角色轮流从环形数组两边拿，本题是1个角色从环形数组两边拿，只能拿N次，而且依照题目 拿走的这 n （=numbers的长度）串香蕉数组起始和末尾连接构成环形。拿香蕉的起始点固定在数组开始或末尾。

所以本题考虑环形数组固定窗口的最大值。left=0，right=n-1。含left的香蕉向右一共顶多到达边界1： left+N-1 ，含right的香蕉向左走一共顶多N个，到达边界2: right-N+1 。

所以题目是求【n-N，0+N-1 】区间内，长度为N固定窗口的最大值。

代码：

import java.util.*;
public class Main{
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums=new int[n];
        for(int i=0;i<n;i++) nums[i]=in.nextInt();
        int k=in.nextInt();
        in.close();
        System.out.println(eat(nums,k));
    }

        private static int eat(int[] nums,int k){
            if(k>=nums.length) return Arrays.stream(nums).sum();
            int n=nums.length;
            int left=n-k, right=n+k-1;
            int sum=0,ans=0;
            for(int i=left,j=0;i<=right;i++,j++){
                sum+=nums[i%n];
                if(j>=k-1){
                    ans=Math.max(ans,sum);
                    sum-=nums[(i-(k-1))%n];
                }

            }
            return ans;
        }
}