Problem Statement Given N heroes with power levels a1, a2....an. You have to partition the heroes with the following rules: 1. Each hero should be part of exactly one partition. 2. Each partition should consist of at least one hero. 3. A partition should consist of only consecutive heroes i.e. if a; and a; (where i<j) are part of the same partition then all a (i < k <=j) should be part of that partition. The strength of the partition is defined as the maximum difference between the power of any two heroes in that partition. You have to partition such that the sum of the strength of partitions is maximum. Output the sum of the strength of partitions. Input format: N a1, a2.....an Constraints: N<=1e6
My initital intuition was DP but obviously it is out of contraints. I have seen many such questions but was not able to solve them.
Is there a link to this problem?
Let's transform the problem a bit. For starters, one can notice that in the optimal solution the partitions will be either increasing or decreasing. Suppose this is false and there's an optimal partition which is neither, but then we could've split the partition into one where min and max are together and some others, which clearly only increases the answer. Now we can interpet the task as: "maximize the sum of $$$|a[l] - a[r]|$$$", because obiously we aren't overcounting this way and by our structure of monotonous partitions we will always have the optimal answer. In order to solve the new task you just have to get rid of modulus and store the max of $$$dp[j]+a[j]$$$ and $$$dp[j]-a[j]$$$ to which you will either add $$$-a[i]$$$ or $$$a[i]$$$ respectively.