### asifthegreat's blog

By asifthegreat, history, 13 months ago, ,

everything seems okay , where is the problem ? can you explain ? problem link : http://codeforces.com/contest/855/problem/B

my code : https://paste.ubuntu.com/25608466/

•
• -21
•

 » 13 months ago, # |   +1 consider this input: 3 1 1 -1 -1 100 1000should output: 1000your solution: -1
•  » » 13 months ago, # ^ |   0 But why ? i was always taking the maximum answer greedily....!!!
•  » » » 13 months ago, # ^ |   0 1 ≤ i ≤ j ≤ k ≤ n.
•  » » » » 13 months ago, # ^ |   0 ooo , may be got it , thank you.
 » 13 months ago, # |   0 As I told you before, greedy approach will not work here. You can try Dynamic programming to solve this type of problem where greedy doesn't work. But for this there is a brute force solution.for each number in the array, let's say that this is aj and we multiply it with q. So we are fixing the middle element every time. Now we have to find ai and ak [i ≤ j and j ≤ k] such that ai * p + ak * r is maximized. So we can easily get an O(n2) solution. How to make it O(n)? Well the array is static. So we can pre-calculate the minimum and maximum in each suffix and prefix of the array and use them instead of running a loop each time to find ai and ak. This is the same solution described in the editorial btw.