A Code

class Solution { public:     int maximumSum(vector<int>& arr) {         const int size = arr.size();         if(size == 0){             return 0;         }         if(size == 1){             return arr[0];         }         vector<int> dp1(size, 0);//max subarray ending with delement i         vector<int> dp2(size, 0);//max subarray ending with deletion of i         dp1[0] = arr[0];         dp2[0] = 0;         int res = arr[0];         for(int i = 1; i < size; i++){             dp1[i] = max(dp1[i - 1] + arr[i], arr[i]);             dp2[i] = max(dp2[i - 1] + arr[i], dp1[i - 1]);       ...

class Solution { public:     /**      * @param prices: a list of integers      * @return: return a integer      */     int maxProfit(vector<int> &prices) {         // write your code here         // 是with transition fee 的延续         //关键是定义状态，（有些累了）         //global[i]表示前i个元素收益。stay at i-th element 几种情况:         //         //1, not sell: global[i] = global[i - 1]         //2, sell: 又分1种情况         //1), 前一天必然可买: global[i] = buy[i - 1] + i-1th 天 prices         //2)         //分析buy[i],         //1,没有交易: = buy[i - 1]         //2,买了(因为有cooldown，需要前一天rest)：= global[i - 2] - prices[i - 1]         // initial: global[0] = 0; buy[0] = -prices[0]. ...

class Solution { public:     /**      * @param prices: a list of integers      * @param fee: a integer      * @return: return a integer      */     int maxProfit(vector<int> &prices, int fee) {         // write your code here         // 双数组DP思想的再次使用：         // f[i]状态表示: 前i个元素最大收益。stay at i-th element:         //1, sell: f[i] = ? + prices[i - 1] - fee. This ? state needs at i-1 th day, have the stock held. This state is the maxProfit that i-1 th day stock was hold. Denote ? as P[i].         //2, not sell: f[i] = f[i - 1];         // now P状态的转移，情况：         // 1，继续hold P[i] = P[i - 1]         // 2，买入 P[i] = f[i - 1] - prices[i - 1].         //初始: f[0] = 0;  P[1] = -prices[0]. P[1] = max(P[0), f[0] - pri...

class Solution { public:     /**      * @param prices: Given an integer array      * @return: Maximum profit      */     int maxProfit(vector<int> &prices) {         // write your code here         // 状态：f[n][k]: f[i][j]前i个元素交易最多j次的最大收益         // 站在元素i向前看。几种情况：         //1, 第i天有交易卖.分两种情况：1）第i-1天卖了 f[i][j] = p[i - 1][j] + diff（这一点很难想到要+diff。可以这么理解f[i][j]是如果做相应的动作的最大收益） 2）第i-1天没有卖。f[i][j] = f[i-1][j-1] + *. *又分为当天买卖和i-1天买 i天卖两种情况 *= max(0, diff)         //2, 第i天没有交易 f[i][j] = f[i-1][j]         // 状态P表示第i天卖了条件下最大交易j次的收益：P[i][j] = max(f[i - 1][j-1] + *, P[i - 1][j] + diff) (注意，其实P[i][j]就是上面分析中第一种情况)         // initial P[0][j]= 0.....         //结果f[n][k]         int n = prices.size();         if(n <= 1...

class Solution { public:     /**      * @param nums: A list of integers      * @param k: An integer denote to find k non-overlapping subarrays      * @return: An integer denote the sum of max k non-overlapping subarrays      */     int maxSubArray(vector<int> &nums, int k) {         // write your code here         //把这道题研究透了。         //首先想到用DP，也想到定义state为f[i][j]表示前i个元素在j个subarray条件下的最大值, i 对应维度 nums，大小nums.size(), j对应维度subarray个数，大小k         //然后，怎么确定transition function是核心。         // 站在nums中的某个元素往前看。[-1, 4, -2, 3],比如-2。有几种可能如下：         //1，-2不放在subarray里。f[i][j] = f[i - 1][j]         //2, -2放在subarray里。又分两种情况1）-2单独组成一个subarray。f[i][j] = f[i -1][j-1] + (-2); 2)-2在前面的subarray里。这个时候发现状态f[i][j]无法实现第二种情况下的状态转移，因为需要一个状态来表示-2前面的一个元素必须在subarray里，即状态P[i][...