You are given an array consisting of $$$n$$$ positive integers. You are standing at the first index, and you want to reach the last index. You can make as many forward jumps as you want. If you jump from index $$$i$$$ to $$$j$$$ your profit is $$$(j - i) \cdot a[i]$$$. What is the maximum total sum of profits that you can achieve?
I created a blog on this topic discussing how the DP optimization for this problem is easier than you think or harder than you think.
https://cfstep.com/training/tutorials/dp/the-hardest-easy-dp-problem/
I solved it in an instant without dp.
here, consider the sum of j-i = n-1 and its some kind of length, a common trick is, we assign i~j-1 value of ai, and we maximum the sum of those values. to do this, we find the prefix maximum of every i(that is the biggest one that it can reaches i, certainly no midterm transfer) and sum it up(certainly, without the last).
you are not smart
the king's new problem bruh
how do you learn?
I realised quickly (and proved) that it's optimal to move to the next larger value. I believe it's just a greedy problem.
how can you comment for smart people while you yourself are a newbie.
Obvious CHT
good to know I wasn't the only one whose first thought was bashing CHT lol
lmao this is barely 1000 rated greedy problem
Isn't this just adding the maximum a[i] in every prefix in O(n)? You can think of always doing the jumps 1 by 1, instead of thinking where exactly you will end up at jumping from position i.
Just use CHT, why use brain when you can easily do it the hard way.
I remember this from the leetcode contest {link}. It is $$$1750$$$-rated on lc, so maybe it would be $$$1100$$$ or so on cf.
Imo, calling it a $$$dp$$$ problem is like saying finding the $$$min$$$ of an array is $$$dp$$$ with transitions $$$dp_i = min(a_i, dp_{i + 1})$$$
Yes, it's not a DP problem per se and can be solved via Greedy (and that's what I mention at the end of the blog in the spoiler section). Of course, I couldn't mention Greedy keyword in the title. The point was to narrow the reader's vision so that they get too involved in the DP keywords that they fail to see the obvious greedy solution (just like the recent Veritasium video where they reword the problem in a way that people become biased).
Maybe the Codeforces crowd is different, but from the LeetCode comments section and from the approximately 30 people that I've asked this problem to, most of them fail to see the greedy once you show them the $$$O(n^2)$$$ DP solution. But if you tell them it was a LeetCode medium problem and it doesn't require DP at all, they immediately come up with the greedy solution.
Formula screams CHT but I believe the answer is just a simple greedy?
Can someone explain how this can be solved using CHT?
become chinese
f(x) = x*arr[i] - arr[i]*i + dp[i]