DP9
Given an array A consisting of n integers , we define beauty of the array as maximum sum of some contiguous elements with performing atmost one operation which is , you can multiply any subarray with ‘x’ but only once.
What will be the maximum subarray sum for this input
N=5,x=-2
A=[-3,8,-2,1,-6]
0
22 <
24
12
multiply the subarray
-2 1 -6 by x
u get
-3 8 4 -2 12
take the sum of
8 4 -2 12
which is 22
that is the answer
the approach is simple, u need to find subarray with minimum sum if x is -ve and multiply that with x
if x is positive find subarray with maximum sum and multiply x with that
handle separately for -1 1 and 0