PROBLEM LINK: ICL1905 Problem - CodeChef
DIFFICULTY: EASY-MEDIUM
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 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.
EXPLANATION
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[0]+C[1]...+C[i].
Then, C[L]+C[L+1]+...+C[R]=prefixSum[R]-prefixSum[L-1].
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.