最近微众银行有一道笔试题为大湮灭
即一个数组删除两个子集后返回数组最大值的问题。
该问题可以看为两个最大子串和的问题，牛客中有人提到可以用前缀和转换为买卖股票问题3，百思不得其解，于是决定先将单个最大子串转换为买卖股票问题。https://leetcode.cn/problems/maximum-subarray/description/
但尝试很久也没成功。目前发现只可以将买卖股票转换为最大子串，方法如下，将买卖股票中使用前缀差，即newprices[i]=prices[i]-prices[i-1],这样的话可以转换为求新数组newprices的最大子数组和问题。
尝试如下
1.dp[i][0]为i位置及及其之前位置上放置左端点的最大值，
dp[i][1]为i位置及其之前位置上放置右端点的最大值。
显然dp[i][0]要么是i位置刚放置左端点后得到最大值，nums[i]>dp[i-1][0]+nums[i];;要么是之前放置时得到的最大值,nums[i]<=dp[i-1][0]+nums[i];
思考：1. dp[i][1]要么是当前位置放置的右端点:dp[i-1][1]+nums[i],要么是之前位置放置的右端点 dp[i-1][1];根据定义取最大值，即dp[i][1]=Math.max(dp[i-1][1],dp[i-1][1]+nums[i]);
2. dp[i][1]要么是当前位置为加入的第一个值,即nums[i]>dp[i-1][1]+nums[i];要么为之前的右端点后移得到的,即nums[i]<dp[i-1][1]+nums[i],要么为之前位置放置的右端点，即dp[i][1]=Max(dp[i-1][1],dp[i-1][1]+nums[i],nums[i]);
上面那种定义是正确的？
no!!!!!! dp[i][1]=Math.max(dp[i-1][1]+nums[i],nums[i]);
这样的话两种状态方程就一样了，实际上定义以某个位置开头计算并无意义，其实际状态方程仍然表达的是以某个位置结束的最大子串。