Contact Form Submission - Suggestion (Silver - More on Prefix Sums)

[maggieliu05]

Someone submitted the contact form!

URL: https://usaco.guide/silver/more-prefix-sums
Module: Silver - More on Prefix Sums
Topic: Suggestion
Message:
I don't believe "Nusret Gokce" problem belongs in the exercices section because it doesn't use prefixsum

[bqi343]

partially agree, though an argument can be made that the solution is similar in structure to the maximum subarray sum solution

[QuicksVolex1]

As a beginner, i would really appreciate if you can explain how that argument can be made. Since i'm struggling to even convince myself the solution works i think that would be really beneficial.

[bqi343]

it's as the editorial describes. you iterate over the array in one direction keeping a running max, then the other.

N, M = map(int, input().split())

S = list(map(int, input().split()))

running_max = 0
for i in range(N):
	running_max = max(running_max - M, S[i])
	S[i] = running_max

running_max = 0
for i in reversed(range(N)):
	running_max = max(running_max - M, S[i])
	S[i] = running_max

print(" ".join(map(str, S)))

[bqi343]

actually, I'll keep this open because this problem needs an internal solution