最大子序和、爬楼梯和买卖股票的最佳时机

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

方法一 暴力破解

思路

从数组最左边开始于数组右边数据依次相加，将相加之后数据进行比较，比较之后最大值为最终结果

详解

1. 创建临时变量 sum 和最大值 maxNumber

2. 从数组子序列左端开始遍历依次取数据

3. 从数组子序列右端开始遍历依次取数据和数组左边数据依次相加

4. 将相加之后值与最大值 sum 进行比较，大的值赋值与 maxNumber

5. 最终获得最大值

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = function (nums) {
  let sum = 0;
  let maxNumber = 0;
​
  for (let i = 0; i < nums.length; i++) { // 从数组子序列左端开始
    for (let j = i; j < nums.length; j++) { // 从数组子序列右端开始
      sum = 0;
      for (let k = i; k <= j; k++) { // 暴力计算
        sum += nums[k];
      }
      if (sum > maxNumber) {
        maxNumber = sum;
      }
    }
  }
  return maxNumber;
};

复杂度分析

• 时间复杂度：$O(n^3)$ 对于每个元素，通过三次遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 $O(n^3)$ 的时间。

• 空间复杂度：$O(1)$​

方法二 动态规划法

思路

数组从左端开始依次和右端数据相加，两数之和为最大数 sum 。下一次相加之后和最大数进行比较，较大数赋值与 sum 由于有负数存在，如果两数相加之后为负数，则两数之和后的最大数为上一个数。

详解

1. 从数组获取第一个值为最大值 sum 和中间值 n

2. 遍历数组，如果中间值n大于0,则和中间值相加，相加结果和最大值比较，较大值赋值与 sum

3. 如果中间值小于0，则将当前值作为中间值

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = function (nums) {
  let sum = nums[0];
  let n = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (n > 0) n += nums[i]; // 判断中间值是否大于0
    else n = nums[i];
    if (sum < n) sum = n; // 相加后的值和最大值作比较
  }
  return sum;
};

复杂度分析

• 时间复杂度：$O(n)$​

  对于每个元素，通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 $O(n)$ 的时间。

• 空间复杂度：$O(1)$​

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例一

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例二

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

方法一 递归法

思路

1. 假设现在输入 $n$ = 10，记作 $f(n)$，那么 10 个台阶 = 9 个台阶 + 走 1 步，此处记作 $f(n-1)$，也可以是 10 个台阶 = 8 个台阶 + 走 2 步，记作 $f(n-2)$​

2. 步骤 1 的 $f(n-1)$ ：9 个台阶 = 8 个台阶 + 走 1 步，也可以是 9 个台阶 = 7 个台阶 + 走 2 步

3. 步骤 1 的 $f(n-2)$：8 个台阶 = 7 个台阶 + 走 1 步，也可以是 8 个台阶 = 6 个台阶 + 走 2 步

4. 以此类推，可以得出递归函数：$f(n) = f(n-1) + f(n-2)$​

详解

从上述思路得出的"递归函数一"如下所示，但是由于执行效率低下，需要进行算法优化。 通常情况下，我们提高执行速度的方式是用"空间换取时间"，顾名思义，占用更多的内存来减少计算时间，请看"递归函数二"： 1. 申请一个Object用于存放已经计算过的楼梯 $map[n]=num$ 2. 每次函数执行前，先判断当前楼层是否已经被计算过，是，则直接从 map 中获得结果；否，则进入计算，并在 map 中记录计算结果

代码

// 递归函数一
const climbStairs = function (n) {
  if (n <= 2) {
    return n;
  } else {
    return climbStairs(n - 1) + climbStairs(n - 2);
  }
};

// 递归函数二
const fn = (n, map) => {
    if(n <= 2) {
      return n
    }
    const result = map[n];
    if(result) {
        return result;
    } else {
      let num = fn(n - 1, map) + fn(n - 2, map);
      map[n] = num;
      return num
    }
}
​
/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = (n) => {
    const map = {};
    return fn(n, map) 
};

• 时间复杂度：$O(2^n)$​

  • 递归函数一，由于每个节点都需要计算，则时间复杂度就等于二叉树的节点数$(2^n-1)$​

  • 经过递归函数二的优化以后，避免了重复的运算，时间复杂度也就变成了二叉树的高度：$O(n)$​

• 空间复杂：$O(n)$​

方法二 动态规划

思路

我们先从给的示例入手，示例中说到： 2个台阶有2种方法，3个台阶有3种方法，那么以此基础。4个台阶：3个台阶走一步或者2个台阶走2步，可以算出 4 个台阶有 3 + 2 = 5 种方法。5个台阶：4个台阶走一步或者3个台阶走2步，也就是 5 + 3 = 8 种方法。以此类推，我们可以发现，这就是经典的斐波那切数列：$f(n)=f(n-1)+f(n-2)$​

详解

1. 申明变量 $result$，记录一些已知结果，比方说：1 个台阶 1 种解法，2 个台阶 2 种解法

2. 为了方便根据数组下标进行查找，在 result 中加一个 0 占位：$result = [0, 1, 2]$;

3. 当输入 n 大于等于 3 时，开始循环计算并记录结果： $result[i] = result[i - 1] + result[i - 2]$;

4. 循环结束后，输出 $result$ 下标为 $n$ 的结果。

代码

const climbStairs = function (n) {
  const result = [0, 1, 2];
  for (let i = 3; i <= n; i += 1) {
    result[i] = result[i - 1] + result[i - 2];
  }
  return result[n];
};

复杂度分析

• 时间复杂度：$O(n)$​

  对 n 进行了一次循环遍历，运行次数与输入 $n$ 成正比

• 空间复杂度：$O(n)$​

  创建了一个长度为 $n$ 的空间，空间复杂度是 $O(n)$​

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

方法一 穷举法

思路

首先，我们想到直观解法，即计算出第 i 天买入，后续所有可能卖出情况下的收益，取最大值即为第 i 天买入可获得的最大收益。

然后比较每一天的最大收益，取最大值，即可得出所有操作中能获取的最大收益。

详解

假设第 i 天当天买入，依次遍历第 i 天之后的所有可能卖出的情况，比较得出收益中的最大值 max。 假设 maxProfit 为当前可以获得的最大收益，初始值为 0，将第 i 天买入收益最大值 max 与 maxProfit 比较，如果 max > maxProfit 则更新 maxProfit 的值，依次进行，最终得到最大收益。

代码

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
  let maxProfit = 0;
​
  function getMax(i) { // 获取第 i 天后股票价格中的最大值
    let max = prices[i + 1];
​
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[j] > max) {
        max = prices[j];
      }
    }
​
    return max;
  }
​
  for (i = 0; i < prices.length - 1; i++) {
    const max = getMax(i) - prices[i]; // 记录第 i 天买入后续合理时间卖出可获得的最大收益
    maxProfit = Math.max(maxProfit, max); // 比较当前已经获取到的最大收益与当天最大收益，取较大者
  }
​
  return maxProfit;
};

复杂度分析

• 时间复杂度：$O(n^2)$​

  我们使用了双重循环计算，内层循环求第 i 天买入后的日子里股票的最高价格，外层循环比较计算最大收益 maxProfit。 那么第一天需要比较 $n - 1$ 次才能求出后续最大价格，第二天比较 $n - 2$ 次，以此类推... 根据等差数列求和公式，最后比较的总次数为 $n * (n - 1) / 2$ ，所以最终得出时间复杂度为 $O(n^2)$。

• 空间复杂度：$O(n)$​

使用长度为 $n$ 的额外数组保存每日可获得的最大收益，即空间复杂度为 $O(n)$​

方法二 求最大差值

思路

再次理解题意，每一天的股票价格组成一个数组，本质上我们只需要寻找一个数组中下标大的数值减去下标小的数值的最大差值即可，而这个差值即为最大收益。

详解

我们先假设最大利润为 maxProfit 和最小成本为 minPrice，令 minPrice 为数组中第一个元素，然后开始遍历数组。

当遍历到某一元素 prices[i] 时： 1. 如果 prices[i] 小于 minPrice，将 prices[i] 的值赋给 minPrice 2. 否则比较 prices[i] - minPrice（此时为非负数）与 maxProfit 的大小 3. 若 prices[i] - minPrice 的值大于 maxProfit，则把新的最大收益值赋给 maxProfit，否则不予处理

最终遍历一次，即可获得最大利润 maxProfit。

代码

function maxProfit(prices) {
  let minPrice = 0;
  let maxProfit = 0;
​
  prices.forEach((price, index) => {
    if (index === 0) { // 初始化最小价格为第一个元素
      minPrice = price;
    } else if (price < minPrice) { // 遍历过程中发现最小价格，则重新赋值
      minPrice = price;
    } else if (price - minPrice > maxProfit) { // 比较当日卖出收益与当前已获取的最大收益
      maxProfit = price - minPrice;
    }
  });
​
  return maxProfit;
};

复杂度分析

• 时间复杂度：$O(n)$​

• 空间复杂度：$O(1)$​

在算法中，我们使用两个公共变量保存最大收益以及最小卖出价格，所以空间复杂度为常数级。

解法三 动态规划

思路

有了解法二的参考，我们还可以利用差分数组连续求和来得出最大收益。第 i 天买入股票，第 i + 1 天卖出，那么我们可以获得的收益为第二天价格与第一天价格相减的差值。

如果差值为正则意味股票在上涨，如果差值为负则意味股票在下跌，我们可以将每日股票的收益转化为差分数组，求出此数组中连续子序列和的最大值，即为最大收益。

详解

根据上述分析，我们用 profits[i] 表示第 i 天进行一笔交易能获得的最大收益，那么第 i 天会产生两种决策：

1. 第 i 天当天买入，此时收益为 0

2. 第 i 天之前买入，第 i 天卖出，此时可获得最大收益为第 i -1 天的最大收益 profits[i - 1] 加上今天股票价格 prices[i] 与昨天价格 prices[i - 1] 的差值

那么第 i 天可以获得的最大收益为这两种情况的最大值，即：profits[i] = max(0, profits[i - 1] + (prices[i] - prices[i - 1]))，

我们只需根据以上公式递推，即可得到每日可获取最大收益数组 profits[]。

我们通过一个变量 maxProfit 来保存已获取的最大收益，然后在计算每日最大收益的过程中与 maxProfit 做比较，最终计算出最大收益。

代码

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
  let maxProfit = 0; // 最大收益
  let profits = [0]; // 每日最大收益存入数组，第一天初始化为 0
​
  for (i = 1; i < prices.length; i++) {
    // 计算每日可获取的最大收益值
    profits[i] = Math.max(0, profits[i - 1] + (prices[i] - prices[i - 1]));
    if (profits[i] > maxProfit) { // 比较该日最大收益与已获取最大收益
      maxProfit = profits[i];
    }
  }
​
  return maxProfit;
};

复杂度分析

• 时间复杂度：$O(n)$​

• 空间复杂度：$O(n)$​