题目要求

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
力扣题目链接

背景

2021年5月 面试字节杭州研发中心后端研发岗位时候一面的面试题
其实2016年11月在北京面试老虎证券时候，面试官也出的是这道题目，遗憾当时没有搞定！

基础版本题目

  1. public  int maxProfit(int[] prices) {
  2.     if (prices.length <= 1) {
  3.         return 0;
  4.     }
  5.     int max = 0;
  6.     for (int x = 0; x < prices.length; x++) {
  7.         for (int y = x + 1; y < prices.length; y++) {
  8.             int temp = prices[x] - prices[y];
  9.             if (temp < 0) {
  10.                 if (Math.abs(temp) >= max) {
  11.                     max = Math.abs(temp);
  12.                 }
  13.             }
  14.         }
  15.     }
  16.     return max;
  17. }
  19. public int maxProfit(int[] prices) {
  20.     if (prices.length <= 1) {
  21.         return 0;
  22.     }
  24.     int min = prices[0], max = 0;
  25.     for (int i = 1; i < prices.length; i++) {
  26.         max = Math.max(max, prices[i] - min);
  27.         min = Math.min(min, prices[i]);
  28.     }
  29.     return max;
  30. }

进阶版本

第一道题目快速写完之后，面试官看写的很快，一次AC。立马让尝试进阶版本题目😅
题目发生了变化，要求可以一天之内多次买卖，追求最大收益。

  1. // 贪心
  2. func maxProfit(prices []int) int {
  3.     profit := 0
  4.     for i := 0; i < len(prices)-1; i++ {
  5.         if prices[i+1] > prices[i] {
  6.             profit += prices[i+1] - prices[i]
  7.         }
  8.     }
  9.     return profit
  10. }
  11. // 动态规划