> For the complete documentation index, see [llms.txt](https://coffe1891.gitbook.io/frontend-hard-mode-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coffe1891.gitbook.io/frontend-hard-mode-interview/id-2/1.-mian-shi-shi-gao-pinlchu-xian-de-suan-fa/2.1.7.md).

# 贰.1.7 实战：阿里巴巴前端面试题

## 贰.1.7.1 求数组子数组之和的最大值

这道题源自微软面试题，后来被阿里巴巴用上了，据说只有20%的人能给出时间复杂度为 $$O(N^3)$$ 的答案，给出 $$O(N)$$ 解的人极少。题目如下：

> 一个有N个整数项的一维数组，这个数组有很连续多子数组，那么子数组之和的最大值是多少？

举例：

* `[ 1,-3, 3, 4, 5,-3]`返回12；
* `[-1,-2,-3,-4,-9,-8]`返回-1；

### 解法一

问题其实是求从下标为`i`和`j`之间的连续数组项之和的最大值。

```javascript
function fn(arr) {
    let maxSum=-Infinity, len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = i; j < len; j++) {
            let sum=0;
            for (let k = i; k <= j; k++) {
                sum += arr[k];
            }
            if (sum > maxSum){
                maxSum = sum;
            }
        }
    }
    console.log(maxSum);
}
fn([ 1, -3,  3,  4,  5, -3]);//>> 12
fn([-1, -2, -3, -4, -9, -8]);//>> -1
```

上面代码有3个for循环，因此时间复杂度是 $$O(N^3)$$ 。

### 解法二

如果注意到 $$A\_i+...+A\_j=A\_i+...A\_j-\_1+A\_j$$ ，那么可以将解法一精简如下：

```javascript
function fn(arr) {
    let maxSum=-Infinity, len = arr.length;
    for (let i = 0; i < len; i++) {
        let sum = 0;
        for (let j = i; j < len; j++) {
            sum += arr[j];
            if (sum > maxSum){
                maxSum = sum;
            }
        }
    }
    console.log(maxSum);
}
fn([ 1, -3,  3,  4,  5, -3]);//>> 12
fn([-1, -2, -3, -4, -9, -8]);//>> -1
```

上面代码第6行就体现了 $$A\_i+...+A\_j$$ ，与解法一的第三个for循环其实是等效的。因此可以精简掉一个for循环，精简之后的算法时间复杂度为 $$O(N^2)$$ 。能做到这样，其实已经不错的，但是还不够，有没有更低时间复杂度的解法呢？有！

### 解法三

若用**动态规划法**，应该先有一个“看起来更加毫无规律”的样本数据，这里选\[ 1, -3, 3, 4, 5, -3]，然后做下面表格分析规律得出**状态转移方程**：

| 步骤 | 操作                  | 累加的子数组之和 | 最大子数组和 |
| -- | ------------------- | -------- | ------ |
| 1  | 加1                  | 1        | 1      |
| 2  | -3                  | -2       | -2     |
| 3  | 之前的和＜0，舍弃，直接从3开始，+3 | 3        | 3      |
| 4  | +4                  | 7        | 7      |
| 5  | +5                  | 12       | 12     |
| 6  | -3                  | 9        | 12     |

用数学归纳法得出状态转移方程如下：

&#x20;//todo

```javascript
function fn(array) {
  if (array == null && array.length <= 0) {
    return 0;
  }
  let Maxsum = Integer.MIN_VALUE;
  let currentSum = 0;
  for (let i = 0; i < array.length; i++) {
    currentSum += array[i];
    if (currentSum < array[i]) {
      currentSum = array[i];
    }
    if (currentSum > Maxsum) {
      Maxsum = currentSum;
    }
  }
  return Maxsum;
}
```

时间复杂度为 $$O(N)$$ 。

## 贰.1.7.2 硬币找零

题目为：

> 从面值为 1,2,5,10 的硬币中找零 36 块钱，最少要 几 枚硬币？

### 解法一：动态规划

这是典型的动态规划问题。所谓动态规划，也即问题分成多个步骤，每一步的选择是可以动态调整的，所有步骤完成之后，最后求最优解。比如求两点之间的最优路径，多种组合方案的最优方案。**这类问题，可以分解成对每一步求最优解，然后将每步的最优解组合，即为最终最优解。**

本题求最少硬币数，也可以用动态规划法求解。首先要归纳出一个**状态转移方程。**&#x7ED9;定的金额`i`，最少硬币数为`f(i)`，硬币面值为`j`，它们之间的关系可以用方程表达如下（该方程即为**状态转移方程**）：

$$
f(i)=f(i-j)+1
$$

有了上面这个状态转移方程，可以看出是一个递归求解过程，所以，此类问题就很好解了，代码如下：

```javascript
/**
 * 硬币找零 之 动态规划法。
 * 状态转移方程 DP(i)=DP(i-j)+1，其中i是金额，j是硬币面值。
 * @param {array} coins 硬币面额的数组
 * @param {number} amount 给定的金额数
 */

(function (coins, amount) {
    //优化，缓存递归过程中已经计算过的金额数
    let cache = new Map();

    //如果金额和面值恰好相等，1枚硬币就能完成
    coins.forEach(coin => {
        cache.set(coin, 1);
    });

    console.time("coffe1891");

    let DP = function (amount) {
        if (amount <= 0)
            return 0;
        else if (cache.has(amount))
            return cache.get(amount);
        else {
            //缓存方案
            let tmpArr = [];
            for (let i = 0; i < coins.length; i++) {
                let coin = coins[i];
                if (amount - coin > 0) {//非法钱数不计算
                    //递归
                    let v = DP(amount - coin) + 1;
                    tmpArr.push(v);
                }
            }

            //从方案中选最优的
            tmpArr.sort((a, b) => a - b);
            cache.set(amount, tmpArr[0]);
            return tmpArr[0];
        }
    }
    console.log("从面值为 " + coins + " 的硬币中找零 " + amount + " 块钱，最少要 " + DP(amount) + " 枚硬币");
    console.timeEnd('coffe1891');
})([1, 2, 5, 10], 36);
```

因此我们发现一个规律：**可用动态规划法解题的关键，在于找到状态转移方程，通过观察该方程，可以更快知道解题的具体算法思路**。

### 解法二：贪心算法

每次我们都优先取最大的硬币面额，直到剩余金额不足最大面额时，我们会取第二大的面额，以此类推，从而实现总硬币数最小的目的。其思想非常简单，我们直接上代码：

```javascript
/**
 * 硬币找零 之 贪心算法
 */
(function (coins, amount) {
    let s = new Date().getTime();
    let greedy = function (amount) {
        let total = 0;//已找金额
        let change = [];//放硬币的罐子
        for (let i = coins.length-1; i >= 0; i--) {
            let coin = coins[i];
            while (total + coin <= amount) {
                change.push(coin);
                total += coin;
            }
        }
        return change.length;
    }
    console.log("从面值为 " + coins + " 的硬币中找零 " + amount + " 块钱，最少要 " + greedy(amount) + " 枚硬币");
    let e = new Date().getTime();
    console.log("耗时  " + (e - s) + "  ms");
})([1, 2, 5, 10], 36);
```