股票的最大利润

---

题目：

基本题意：找到差值最大的返回差值

题解

1、暴力法

• 解题思路：暴力双层遍历找到差值最大的返回差值

• 复杂度分析：

  • 时间复杂度O(n^2)：双层循环
  • 空间复杂度O(1)

• 代码：

  // 暴力遍历
  class Solution {
      public int maxProfit(int[] prices) {
  
          int max = 0;
          // 暴力找到差值最大的返回差值
          for (int i = 0; i < prices.length; i++) {
              for (int j = i + 1; j < prices.length; j++) {
                  if ((prices[j] - prices[i]) > max ){
                      max = prices[j] - prices[i];
                  }
              }
          }
  
          return max;
      }
  }

2、一次遍历（动态规划法）

• 解题思路：前 i 日最大利润=max(前 (i−1) 日最大利润,第 i 日价格 − 前 i 日最低价格)

• 复杂度分析：

  • 时间复杂度 O(N) ： 其中 N 为 prices 列表长度，动态规划需遍历 prices 。
  • 空间复杂度 O(1) ： 变量 min和 max 使用常数大小的额外空间。

• 代码：

  // 一次遍历，动态规划
  class Solution2 {
      public int maxProfit(int[] prices) {
          int min = Integer.MAX_VALUE;
          int max = 0;
          for (int i = 0; i < prices.length; i++) {
              // 一步一步进行，判断如果该值小于最小值，就成为最小值，否则，判断该值与最小值只差是否大于目前差值最大值，大于就将差值付给他
              if (prices[i] < min) {
                  min = prices[i];
              }else if (prices[i] - min > max) {
                  max = prices[i] - min;
              }
          }
          return max;
      }
  }

• 优化代码：

  class Solution {
      public int maxProfit(int[] prices) {
          int min = Integer.MAX_VALUE;
          int max = 0;
          for ( int price : prices) {
              // 一步一步进行，判断如果该值小于最小值，就成为最小值，否则，判断该值与最小值只差是否大于目前差值最大值，大于就将差值付给他
              min = Math.min(min,price);
              max = Math.max(max,price - min);
          }
          return max;
      }
  }