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;
}
}