面试官在“逗”你系列：连续子数组的最大和或最小和

前言

本文题目是“连续子数组的最大和或最小和”。

话不多说，开始“打怪”修炼...

一、理解题目

以“连续子数组的最大和”为例，相当于我们在数组中，计算连续的子数组的和，找寻最大值。如在数组[3, -2, 1, 2, 4, -6, 5]中连续子数组的最大和为：3 + (-2) + 1 + 2 + 4 = 8

1输入：[3, -2, 1, 2, 4, -6, 5]
2输出：8

一定要准确的理解题意，如不是特别明确，建议与面试官再次沟通确认，避免需求与实现不一致的情况。

二、解决方案

连续子数组的最大和

这道面试题有几种解决方案呢？可能在很多个同学的脑海里会出现这样的一种方案：

1. 求连续子数组组合方案：

将数组中的元素进行连续子数组的组合，每一种组合计算出一个值，依次比较后取出最大值。那这种方式是可以肯定是可以最终的效果的，But这么处理的话，会有多少种组合方案呢？

1以数组 [1, -1, 2, -3, 5]为例：
2	连续子数组有：N + (N-1) + (N-2)...  +  1 = n*(n+1) / 2

随着数组长度N的值越大，组合数量肯定是越大！同时在获取阶乘后，还需要再次进行一次最大值得比较。

划重点：

此方案虽可以实现最终的效果，但是确实十分不可取的!

2. 最优解方案

在面试时面试题除了固定的套路和算法外，要多尝试逻辑思维的转变...

1技术方案：
2	1. 初始化两个变量：sum(连续子数组的累加和)、max(最大值)
3	2. 遍历数组元素，考虑sum的情况： 
4		sum >= 0，将当前元素的值进行累加
5		sum < 0，注意，sum的值为负值，不管当前的元素值是什么，累加sum(负数)肯定值最终会变小的，所以此刻，要重新对sum进行赋值操作
6	3. 每次遍历时，都要比较sum和max的大小， 如果 sum > max，进行赋值max = sum
7	4. 返回最终的结果max

接下来，我们来看下代码的实现：

1/**
2 * getGreatestSumOfSubArray()
3 * @description 获取连续子数组中最大和
4 * @param Array arr 指定的数组
5 * @returns Number sum 最大和
6*/
7function getGreatestSumOfSubArray (arr) {
8  // 容错边界处理
9  if (!Array.isArray(arr) || arr.length === 0) {
10    return 0
11  }
12
13  // 解构，初始获取数组的第一个元素值
14  // 注意：一定不能把sum和max设置初始化为0，必须要考虑数组元素中全部为负数的情况
15  let [ sum ] = arr
16  let [ max ] = arr
17  
18  let len = arr.length
19  for (let i = 1; i < len; i++) {
20    // 如果当前sum累加 < 0，重新初始化当前元素值；否则执行累加
21    if (sum < 0) {
22      sum = arr[i]
23    } else {
24      sum += arr[i]
25    }
26
27    // 比较累加和与最大值
28    if (sum > max) {
29      max = sum
30    }
31  }
32  
33  return max
34}
35
36// 调用
37let max = getGreatestSumOfSubArray([3, -2, 1, 2, 4, -6, 5])
38console.log(max) // 8

OK，这样我们就实现了需求，小朋友，你还有问号吗？

连续子数组的最小和

“连续子数组的最小和” 这个需求的实现原理和“连续子数组的最大和”的实现基本是一致的，唯一的区别点为：当sum的值 > 0为正数时，累加就无意义了，需要重新赋值为当前值。我们来看下代码的实现

1/**
2 * getLeastSumOfSubArray()
3 * @description 获取连续子数组的最小和
4 * @param Array arr 指定的数组
5 * @returns Number min 最小和
6*/
7function getLeastSumOfSubArray (arr) {
8  if (!Array.isArray(arr) || arr.length === 0) {
9    return 0
10  }
11
12  // 初始化
13  let [ sum ] = arr
14  let [ min ] = arr
15
16  // 遍历数组元素，如果sum是一个正数，累加就无意义，重新赋值为当前项；
17  let len = arr.length
18  for (let i = 1; i < len; i++) {
19    if (sum > 0) {
20      sum = arr[i]
21    } else {
22      sum += arr[i]
23    }
24    if (sum < min) {
25      min = sum
26    }
27  }
28
29  return min
30}
31
32let min = getLeastSumOfSubArray([-1, -2, 3, 2, -4, -8])
33console.log(min) // -12 = (-4) + (-8)

这个了解了不...

后记

以上就是胡哥今天给大家分享的内容，喜欢的小伙伴记得点赞、收藏呀，关注胡哥有话说，学习前端不迷路，欢迎多多留言交流...

胡哥有话说，专注于大前端技术领域，分享前端系统架构，框架实现原理，最新最高效的技术实践！