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.