Couple of days ago I gave a test where this question was asked and I couldn’t solve it.
You’re given an array and you have to find a subarray with maximum sum (Pretty standard problem) but this problem was bit modified, you’ll be given a number X such that -500 <= X <= 500 and you can multiply every element of any subarray with X only once and then find the maximum sum of a subarray.
Here are some test cases-
Input- (the first line contains N and X)
5 5
1 2 3 4 5
Output- 75 (mutliply every element with 5)
Input-
5 -1
-10 -10 -10 10 10
Output-
50 (multiply first 3 element with X and then subarray with maximum sum would be entire array)
I thought of multiplying every negative element with X if X<=0 and every positive element with X if X>0 but this will change all the elements in between (both positives and negatives) because I have to multiply each element of a subarray with X, So I couldn’t proceed further and couldn’t think of any solution with time complexity O(N) or O(NlogN)
Can anyone help me as how to solve this?
We can do this multiplication to only one subarray? If yes,
Use the regular algorithm to find the maximum sum subarray and the minimum sum subarray. (Note that they can be negative too). Now multiply both of them with x, and return the maximum out of the four. (The two values before multiplying, and the two after multiplying). If multiplication is a choice. If we are forced to multiply, then return the max of the multiplied values.
3 Likes
Use 3 dps.
Let dp1_i denote the largest suffix of i such that we haven’t multiplied any element with X, Let dp2_i denote the the largest sum such that we have multiplied a suffix of i with X, and dp3_i be the largest sum such that we have multiplied any subarray with X.
1 Like
Will the method that I suggested work? I feel it is optimal to multiply the already largest possible sum subarray with x (assuming x is positive and the largest subarray sum is also positive).
If x is negative, we can just flip all the signs and do the same.
2 Likes
If X > 0, your algo is correct…but if X < 0, I think(if I understood your logic correctly) your algo fails on this:
A = [-3, 8, -2, 1, 6] , X = -1
Max Subarray Sum(without X) = 13
Min Subarray Sum(Without X) = -3
max(13, -3, -13, 3) = 13 but optimal answer is 17(multiply -2 with -1)
2 Likes
Yes, That algo won’t give us the maximum answer I guess.
it was asked in coding ninja
Yes, and I couldn’t do it.
Yeah that’s right. I thought we could invert the sign of the given array and run the same algorithm if x < 0. But that doesn’t seem to work. I guess dp is the way!
1 Like
did you get the mail today for round 2 result
They said results are out but I’ve not received any mail yet. Have you?
if your score is greater than equal to 200 then you are qualified
i also didnot get the mail
no i think cutoff is 300 or so
Results are not declared yet I have a pdf of all the qualified participants
can you share the pdf if u wish
Then I’m not clearing it, I solved only first 2 problems.
