PROBLEM LINK: https://www.codechef.com/problems/ICL1905
DIFFICULTY: EASYMEDIUM
PROBLEM
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 ith 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.
EXPLANATION
For any segment [L,R], the profit is A*(RL+1)C[L]C[L1]...C[R]gap(L,R).
To compute C[L]+...+C[R], we compute a prefixSum array where prefixSum[i]=C[0]+C[1]...+C[i].
Then, C[L]+C[L+1]+...+C[R]=prefixSum[R]prefixSum[L1].
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.