How to Maximize Continuous Blockchain File Dump onto a SATA Disk

Problem Description

The blockchain storage layer is a chain of N files with sizes F1, F2, …, Fn. Only consecutive files can be dumped onto a cheap SATA disk, and the total size of the dumped files must not exceed the disk capacity M. Compute the maximum possible sum of a contiguous block of files that fits.

Input

First line: the SATA disk capacity M (1000 ≤ M ≤ 1000000).

Second line: the sequence of file sizes F1, F2, …, Fn, where 1 ≤ n ≤ 100000 and 1 ≤ Fi ≤ 500.

Output

The maximum sum of a contiguous subsequence that does not exceed M.

Examples

Example 1

1000
100 300 500 400 400 150 100

Output: 950 (subsequence [400, 400, 150]).

Example 2

1000
100 500 400 150 500 100

Output: 1000 (subsequence [100, 500, 400]).

Solution Idea – Sliding Window

Key Questions

Q1: For each right pointer, what operation is performed?

Q2: When should the left pointer move right, and what does the while‑loop maintain?

Q3: When is the answer updated?

Answers

A1: Add the current element num to the window sum win_sum.

A2: While win_sum > M, subtract the element at the left pointer ( left_num) from win_sum and increment left until win_sum ≤ M.

A3: Whenever win_sum ≤ M (typically after the left pointer has moved), update the answer with ans = max(ans, win_sum).

Reference Implementation (Python)

M = int(input())
lst = list(map(int, input().split()))

ans = 0
win_sum = 0
left = 0

for right, num in enumerate(lst):
    # A1: add current number to window sum
    win_sum += num
    # A2: shrink window from the left while exceeding capacity
    while win_sum > M:
        win_sum -= lst[left]
        left += 1
    # A3: update maximum feasible sum
    ans = max(ans, win_sum)

print(ans)

Complexity Analysis

Time complexity: O(N) – a single pass through the array.

Space complexity: O(1) – only a few constant‑size variables are used.