_1746.java

package com.fishercoder.solutions.secondthousand;

public class _1746 {
    public static class Solution1 {
        /*
         * credit: https://leetcode.com/problems/maximum-subarray-sum-after-one-operation/discuss/1049224/Java-O(n)-Time-O(n)-Space-DP-solution
         */
        public int maxSumAfterOperation(int[] nums) {
            int len = nums.length;
            // dp[i][0] means the sum of all elements in the subarray up to index i without any
            // number squared
            // dp[i][1] means the sum of all elements in the subarray up to index i with nums[i]
            // squared
            // esentially, there are three dimensions:
            // 1. the element nums[i] squared itself might be the biggest sum of subarray itself;
            // 2. the subarray sum without any elemtns squared + nums[i] squared
            // 3. the subarray sum with one element prior to i square + nums[i]
            int[][] dp = new int[len][2];
            dp[0][0] = nums[0];
            dp[0][1] = nums[0] * nums[0];
            int maxSum = dp[0][1];
            for (int i = 1; i < len; i++) {
                dp[i][0] = Math.max(dp[i - 1][0] + nums[i], nums[i]);
                dp[i][1] =
                        Math.max(
                                nums[i] * nums[i],
                                Math.max(dp[i - 1][0] + nums[i] * nums[i], dp[i - 1][1] + nums[i]));
                maxSum = Math.max(maxSum, dp[i][1]);
            }
            return maxSum;
        }
    }
}