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?