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?