https://www.acmicpc.net/problem/21758
initial
Well i thought maybe this is a 2d dp table question so i tried deducing the logic but to no avail. But in my initial attempt, i realised that for both bees to collect as much honey, the honey needs to be placed at the far end of the list because the bees will travel up till the honey and not beyond that index. But i didnt know how to solve so i googled.
So upon googling, it is correct that we can find 2 patterns (there is 1 more but wait). Honey can be placed on the leftmost or rightmost end of the list and we can get bee bee honey pattern or honey bee bee pattern. We fixate the leftmost or rightmost bee and move the second bee with a for loop. Using a precalculated prefix sum, (and some logic deduction with pen and paper), we can see that the fixed bee we can just do prefix_sum minus the lst[i] whereas the iterating bee we do prefix_sum minus prefix_sum[i].
But there is 1 more pattern. There could be bee honey bee pattern. Maybe the leftmost and rightmost values have high values so we want honey to be placed at that index, not the bee cuz if bee is placed there we cant get the honey. This logic is rather simple we just add front prefix [i] and back prefix [i] tgt.
solution
n = int(input())
lst = list(map(int, input().split()))
front, back = [0 for _ in range(n)], [0 for _ in range(n)]
for i in range(n):
if i == 0:
continue
front[i] = lst[i] + front[i - 1]
back[n - 1 - i] = lst[n - 1 - i] + back[n - i]
ans = 0
# Bee bee honey
for i in range(1, n - 1):
bee1 = front[n - 1] - lst[i]
bee2 = front[n - 1] - front[i]
ans = max(bee1 + bee2, ans)
# Honey bee bee
for i in range(n - 2, 0, -1):
bee1 = back[0] - lst[i]
bee2 = back[0] - back[i]
ans = max(bee1 + bee2, ans)
# Bee honey bee
for i in range(1, n - 1):
bee1 = front[i]
bee2 = back[i]
ans = max(bee1 + bee2, ans)
print(ans)complexity
n time and space cuz even max() is n time. It is sort that is n log n
