Maximum Subarray Sum After One Operation

给一个数组, 可以把其中一个数平方, 求这个数组可能的子数组的最大和.

这个和上个题好像差不多, 我用dp做的, 主要是要看出来转移方程,即, 因为只能做一次平方. 所以选择了当前的数做了平方后, 以后的数字不可以再做, 以后的数就是普通的子数组最大和.

class Solution {
    public int maxSumAfterOperation(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n + 1][2];
        for(int i = 1; i <= n; i++) { 
            dp[i][0] = Math.max(dp[i - 1][0] + nums[i - 1], dp[i][0]);
            dp[i][1] = Math.max(dp[i - 1][1] + nums[i - 1], dp[i - 1][0] + nums[i - 1] * nums[i - 1]);
        }
        int res = Integer.MIN_VALUE;
        for(int i = 0; i <= n; i++) {
            int local = Math.max(dp[i][0], dp[i][1]);
            res = Math.max(res, local);
        }
        return res;
    }
}