区块链底层存储是一个链式文件系统,由顺序的 N 个文件组成,每个文件的大小不一,依次为F1, F2, …, Fn 。随着时间的推移,所占存储会越来越大。云平台考虑将区块链按文件转储到廉价的 SATA 盘,只有连续的区块链文件才能转储到 SATA 盘上,且转储的文件之和不能超过 SATA 盘的容量。假设每块 SATA 盘容量为 M,求能转储的最大连续文件大小之和。
输入描述:
第一行为 SATA 盘容量 M,1000 ≤ M ≤ 1000000
第二行为区块链文件大小序列 F1, F2, …, Fn。其中 1 ≤ n ≤ 100000,1 ≤ Fi ≤ 500
输出描述:求能转储的最大连续文件大小之和。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int setaSize = sc.nextInt();
sc.nextLine();
String[] sizesString = sc.nextLine().split("[ ]");
int[] sizes = new int[sizesString.length];
for(int i = 0;i < sizesString.length;i++){
sizes[i] = Integer.parseInt(sizesString[i]);
}
int left = 0,right = 0;
int max = 0;
int sum = 0;
while(right < sizes.length){
if(sum == setaSize){
max = setaSize;
break;
}
if(sum < setaSize){
max = Math.max(sum,max);
sum += sizes[right];
right++;
}
while(sum > setaSize){
sum -= sizes[left];
left++;
}
}
System.out.print(max);
}
}