https://codeforces.com/contest/1155/problem/D
This problem is similar to yesterdays atcoder regular contest problem A, where i used the logic that if X>0 we multiply the maximum segment and if X<0 we multiply the minimum segment but if i use the same logic in this question it is giving WA on test 10. Can someone pls help me understand why it doesn't work here?
This logic would've worked for $$$x>0$$$, but may not work for negative values of $$$x$$$, since in these scenarios, it may be more beneficial to multiply a segment of the chosen subarray instead.
For instance, consider the array $$$a = [2, -2, 2]$$$ and $$$x = -1$$$. The minimum subarray in $$$a$$$ would be $$$[-2]$$$, and the answer derived would be $$$-2\times -1 = 2$$$. However, a more optimal solution would be to multiply the $$$-2$$$ by $$$-1$$$ and choose the entire array (which is now $$$[2, 2, 2]$$$) to be summed, yielding a result of $$$6$$$.
I didn't got the example part in both the scenarios u are multiplying -2 with -1 only right? What I'm doing is im finding the minimum sum subarray and multiplying it with X and then again running kadanes algo on top of that https://codeforces.com/contest/1155/submission/252016885 For the example u gave it is indeed returning 6
Sorry for misunderstanding your algorithm. However, the maximum sum obtainable using this algorithm may still not be optimal.
For instance, consider the following example: $$$a = [5, -6, 7, -9]$$$ and $$$x = -1$$$. After the transformation, $$$a$$$ would equal $$$[5, -6, 7, 9]$$$, where the optimal sum is $$$7+9=16$$$. However, a better solution in this case is to multiple $$$[-6]$$$ instead, yielding $$$[5, 6, 7, -9]$$$ whose maximal subarray sum is $$$18$$$.
Right got it.. so basically finding the max subarray after transformation makes this question difficult Thanks:)