题解 | 空间跃迁
空间跃迁
https://www.nowcoder.com/practice/e6ff2b0bf309412fb491e3276fb9f305
这题其实就是求前缀和
要找出加起来最大的那一段序列，序列长度为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);
}
}