122. 买卖股票的最佳时机 II

难度简单1108
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

  1. public int maxProfit(int[] prices) {
  2.         int n = prices.length;
  3.         int[][] dp = new int[n][2];
  4.         dp[0][0] = 0;
  5.         dp[0][1] = -prices[0];
  6.         for (int i = 1; i < n; ++i) {
  7.             dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
  8.             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
  9.         }
  10.         return dp[n - 1][0];
  11.     }
  13. 作者：LeetCode-Solution
  14. 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/

优化

  1. public int maxProfit(int[] prices) {
  2.         int n = prices.length;
  3.         int dp0 = 0, dp1 = -prices[0];
  4.         for (int i = 1; i < n; ++i) {
  5.             int newDp0 = Math.max(dp0, dp1 + prices[i]);
  6.             int newDp1 = Math.max(dp1, dp0 - prices[i]);
  7.             dp0 = newDp0;
  8.             dp1 = newDp1;
  9.         }
  10.         return dp0;
  11.     }
  13. 作者：LeetCode-Solution
  14. 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/

image.png

  1. public int maxProfit(int[] prices) {
  2.         int ans = 0;
  3.         int n = prices.length;
  4.         for (int i = 1; i < n; ++i) {
  5.             ans += Math.max(0, prices[i] - prices[i - 1]);
  6.         }
  7.         return ans;
  8.     }
  10. 作者：LeetCode-Solution
  11. 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/

解析

image.png
优化易懂版

  1. public int maxProfit(int[] prices) {
  2.         int len = prices.length;
  3.         if (len < 2) {
  4.             return 0;
  5.         }
  7.         int res = 0;
  8.         for (int i = 1; i < len; i++) {
  9.             int diff = prices[i] - prices[i - 1];
  10.             if (diff > 0) {
  11.                 res += diff;
  12.             }
  13.         }
  14.         return res;
  15.     }
  17. 作者：liweiwei1419
  18. 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/

解析
贪心算法 在每一步总是做出在当前看来最好的选择。

「贪心算法」 和 「动态规划」、「回溯搜索」 算法一样，完成一件事情，是 分步决策 的；
「贪心算法」 在每一步总是做出在当前看来最好的选择，我是这样理解 「最好」 这两个字的意思：
「最好」 的意思往往根据题目而来，可能是 「最小」，也可能是 「最大」；
贪心算法和动态规划相比，它既不看前面（也就是说它不需要从前面的状态转移过来），也不看后面（无后效性，后面的选择不会对前面的选择有影响），因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的；
这道题 「贪心」 的地方在于，对于 「今天的股价 - 昨天的股价」，得到的结果有 3 种可能：① 正数，
② 0，③负数。贪心算法的决策是： 只加正数 。

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/