动态规划——Best Time to Buy and Sell Stock III

题意：用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。如果最多进行两次交易，但必须在买进一只股票前清空手中的股票，求最大的收益。

示例 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
示例 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
示例 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

之前有一个Best Time to Buy and Sell Stock I ，比这个题简单点儿，那个题是最多一次操作，求最大的收益。同样是使用动态规划，由于这次允许最多两次操作，只需要分两次，

将输入的整个周期通过for对周期长度限制（第一个子周期长度递增且不超过原周期长）并分割成两个子周期先后进行dp数组的递推即可。

 int maxProfit(int* prices, int pricesSize) {

      int ans = ;

     if (pricesSize > ){

         int*dp = (int*)malloc(pricesSize*sizeof(int));

         dp[] = ;

         int ans2 = ;

         for (int i = ; i <= pricesSize; i++){

             dp[] = ;

             ans2 = ;

             for (int j = ; j<i; j++){

                 dp[j] = (prices[j] + dp[j - ] - prices[j - ]) >  ? (prices[j] + dp[j - ] - prices[j - ]) : ;

                 ans2 = ans2 >= dp[j] ? ans2 : dp[j];

             }

             ans = ans >= ans2 ? ans : ans2;

             if (i < pricesSize)dp[i] = ;

             for (int k = i+; k<pricesSize; k++){

                 dp[k] = (prices[k] + dp[k - ] - prices[k - ]) >  ? (prices[k] + dp[k - ] - prices[k - ]) : ;

                 ans = ans >= (dp[k]+ans2) ? ans : (dp[k]+ans2);

             }

         }

         //free(dp);

     }

     else if (pricesSize == ){

         ans = (prices[] - prices[]) >  ? (prices[] - prices[]):;

     }

     else ans = ;

     return ans;

 }

但是非常搞笑的是我这个代码虽然在LeetCode上成功AC，但是应该是最差的一个解决方案。。。但是思路上非常便于理解

巴特西

动态规划——Best Time to Buy and Sell Stock III

最新文章

热门文章