After getting destroyed by the problem mentioned in this blog
I decided to get revenge on the problemsetter(dvdg6566) by setting a problem related to his that he couldn't solve :). After thinking a while I came up with this problem. Given two integers N and I, construct a sequence of non-negative integers with length N with inequality I where inequality is defined as
$$$I = \sum\limits_{i=1}^N \bigg( \sum\limits_{j=i}^N rangemax(i,j) \bigg)$$$
But after thinking a while again, I realized I couldn't solve it either. I could only construct a solution for $$$I>=(2*(n-1)*(n-2))$$$ but for smaller I, I have no idea how to do it. Any help would be appreciated thanks!.
Zane you are a simp
Could you shed more light on how the transition would look?
I'm unable to wrap my head around the fact that the position of
maxvaluein thelengthsized array isn't necessary.Thank you!
Transition:
Option 1: We don't take the max value. then $$$dp(i,j,k) = dp(i,j,k-1)$$$.
Option 2: We take the max value. Iterating all possible positions, we can find the remaining $$$I$$$ to be spread over left and right side. Try breaking in all ways.
Hence transition is $$$O(N^3)$$$.
If the blog gets more upvotes than your comment I will go solve the original problem