描述

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

链接

122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn.com)

 

解法

本题首先要清楚两点：

• 只有一只股票！
• 当前只有买股票或者买股票的操作

想获得利润至少要两天为一个交易单元。

#对于贪心算法而言

想到其实最终利润是可以分解的

• 假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。
• 相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
• 此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
• 那么根据prices可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

局部最优：收集每天的正利润，全局最优：求得最大利润。

 1 class Solution {
 2     // 思路1：贪心算法,时间复杂度 O(n),额外空间复杂度 O(1)
 3     public int maxProfit1(int[] prices) {
 4         int res = 0;
 5         for (int i = 1; i < prices.length; i++) {
 6             res += Math.max(prices[i] - prices[i - 1], 0);
 7         }
 8         return res;
 9     }
10 
11     // 思路2：动态规划,时间复杂度 O(n),额外空间复杂度 O(n)
12     public int maxProfit(int[] prices) {
13 
14         // [天数][是否持有股票]
15         int[][] dp = new int[prices.length][2];
16 
17         // base case
18         dp[0][0] = 0;
19         dp[0][1] = -prices[0];
20 
21         for (int i = 1; i < prices.length; i++) {
22             // dp公式
23             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
24             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
25         }
26         return dp[prices.length - 1][0];
27     }
28 }

 

参考

carl