题解 | 空间跃迁

这题其实就是求前缀和

要找出加起来最大的那一段序列，序列长度为k-1，因为要与实际一致

需要特判当k>=n的情况，因为这种情况不需要消耗时间，但是不特判就会输出全部加起来的值

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt()-1;
		int k=scanner.nextInt();
		long s[]=new long[n+1];
		for (int i = 1; i <= n; i++) {
			s[i]=s[i-1]+scanner.nextLong();
		}
		long max=0;
		if(k>=n) {
			s[n]=0;
		}
		for (int i = 1,j=i+k-1; j < n&&j>=i; i++,j++) {
			if(k==0)break;
			if(max<s[j]-s[i-1]) {
				max=s[j]-s[i-1];
			}
		}
		System.out.println(s[n]-max);

	}

}