### Problem Discussed Today:

Interview Problem ( From LeetCode )

No editorial will be provided for the Interview Problem.

Editorial

Idea:

If there is at least a prefix or a suffix with non-positive sum, we can delete that prefix/suffix and end up with an array with sum ≥ the sum of the whole array. So, if that's the case, the answer is "NO".

Otherwise, all the segments that Adel can choose will have sum < than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Idea:

For each window $(x,y$ dirty water may reach it through windows $(x-1,y-1$ or $(x-1,y)$ or $(x-1,y+1)$.
For each window $(x,y)$ let’s denote by $d{p}_{x,y}=t$ the latest moment $t$ such that some window $\left(p,q\right)$ was cleaned at moment $t$ and the dirty water reached $(x,y)$ from $\left(p,q\right)$.
We previously stated that dirty water may reach $\left(x,y$ only from its neighbors. Quite frankly:
$t=d{p}_{x,y}=max\left(d{p}_{x-1,y-1},d{p}_{x-1,y},d{p}_{x-1,y+1}\right)$
Because these are the only possible ways such that the dirty water may reach $(x,y)$.
Now that we have found $t$ for our window $\left(x,y\right)$. If $t$ is later than $A_{x,y}$ then it will be dirty by the end of the process, otherwise it will be clean.
After determining the answer for $(x,y)$ (clean/dirty) we should update $dp_{x,y}$:
$d{p}_{x,y}=max\left(d{p}_{x,y},{A}_{x,y}\right)$
Because $d{p}_{x,y}$ denotes some moment where dirty water reaches $(x,y)$ and it will be propagated to windows below $\left(x,y\right)$. At the moment, $A_{x,y}$ the window will be cleaned and dirty water will start flowing, so we must update $d{p}_{x,y}$ such that $A_{x,y}$ would be propagated as well.