CodeCraft-22 Problem D Editorial

[@kaustav07]

This explanation is pure GOLD.

[@amateursoundz6262]

Agreed, explanations like these should be mandatory for all problemsetters.

[@amateursoundz6262]

I suddenly feel much less intimidated by segment trees. I now see that they are just a tool.

[@vishwajeetjangra3390]

A quality problem, so much to learn from it.

[@0chunhui]

Hi, could help me find out why my thought is wrong? My idea is for every index i, calculate the max sum of subarrays that are end at index i, so if the max element in the subarray is less than the max sum, the answer is no, otherwise yes.
The code is like this:
void solve() {
int n; cin >> n;
vector a(n);
for(int i=0; i> a[i];
ll cur = -1e18, nax = -1e18;
for(int i=0; i= cur + a[i]) {
cur = a[i];
nax = a[i];
} else {
cur += a[i];
nax = max(nax, a[i]);
}
if(nax < cur) {
cout

[@Sksahu_123]

great q

[@sarthakgokhale1062]

very good quality question

[@aayushchhabra9805]

i guess with prefix array we can also make a greater next element sort of thing to check the conditions like x>0 for then range (i+1,next_greater for ith index)

[@shreyashachoudhary480]

Great explanation & problem! Btw which app you are using? Seems some linux interface.

[@viditjain7246]

Thanks! :)
I had used Xournal++ for the illustrations and OBS studio to record it on Linux

[@harshalgawai746]

@@viditjain7246 Yes I have used it too. Its really good. Very good explanation Vidit. Thank you.