PROBLEM LINK: https://www.codechef.com/problems/ICL1905
Given N planets, you can visit any subsegment of planets so as to gain profit. The costs associated with each visit are as follows:
For each planet you visit, you gain A coins.
For the i-th planet you visit, you lose C[i] coins.
If you visit the segment [L,R], you have to pay gap(L,R) coins such that gap(L,R)=max[(D[r]−D[l])^2] where L<=l<=r<=R.
Find the maximum profit that you can achieve.
For any segment [L,R], the profit is A*(R-L+1)-C[L]-C[L-1]-...-C[R]-gap(L,R).
To compute C[L]+...+C[R], we compute a prefixSum array where prefixSum[i]=C+C...+C[i].
To compute the gap(L,R), we may first notice that gap(L,R) is maximum when |D[l]-D[r]| is maximum. This is maximum for the case where D[l]=max(L,R) and D[r]=min(L,R) where max(L,R) represents the maximum element of D in the range [L,R] (similarly for min(L,R)). To compute gap(L,R) efficiently,we can manage the max and min for each segment while iterating over R for a given value of L.
Then the profit can be found for each segment in O(1) time and iterating over all segments, we can find the maximum profit in O(n^2) time.