You are given an integer array nums. You must perform exactly one operation where you can replace one element nums[i] with nums[i] * nums[i].
Return the maximum possible subarray sum after exactly one operation. The subarray must be non-empty.
Example 1:
Input: nums = [2,-1,-4,-3]
Output: 17
Explanation: You can perform the operation on index 2 (0-indexed) to make nums = [2,-1,16,-3]. Now, the maximum subarray sum is 2 + -1 + 16 = 17.
Example 2:
Input: nums = [1,-1,1,1,-1,-1,1]
Output: 4
Explanation: You can perform the operation on index 1 (0-indexed) to make nums = [1,1,1,1,-1,-1,1]. Now, the maximum subarray sum is 1 + 1 + 1 + 1 = 4.
implSolution{#[allow(dead_code)]pubfnmax_sum_after_operation(nums:Vec<i32>)->i32{// Here f[i] represents the value of max sub-array that ends with nums[i] with no substitutionletmutf=0;// g[i] represents the case with exact one substitutionletmutg=0;letmutret=1<<31;// Begin the actual dp processforein&nums{// f[i] = MAX(f[i - 1], 0) + nums[i]letnew_f=std::cmp::max(f,0)+*e;// g[i] = MAX(MAX(f[i - 1], 0) + nums[i] * nums[i], g[i - 1] + nums[i])letnew_g=std::cmp::max(std::cmp::max(f,0)+*e**e,g+*e);// Update f[i] & g[i]f=new_f;g=new_g;// Since we start at 0, update answer after updating f[i] & g[i]ret=std::cmp::max(ret,g);}ret}}