### 650iq's blog

By 650iq, history, 2 months ago,

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?

• 0

 » 2 months ago, # | ← Rev. 2 →   0 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$.
•  » » 2 months ago, # ^ |   0 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
•  » » » 2 months ago, # ^ |   0 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$.
•  » » » » 2 months ago, # ^ |   0 Right got it.. so basically finding the max subarray after transformation makes this question difficult Thanks:)