前端练习10 连续子串最大和

求连续子串最大和的练习。

题目

输入一组整数,例如:[-23, 17, -7, 11, -2, 1, -34, 2, -21, 9, 12],求出子序列的最大和

实现1

先尝试一种最暴力的方法,求最大子串,那么就将所有的子串计算出来,然后从中选出最大的

1
2
3
4
5
6
7
8
9
10
11
12
const getMax = arr => {
let result = [];
let temp;
for (let i = 0; i < arr.length; i++) {
temp = 0;
for (let j = i; j < arr.length; j++) {
temp += arr[j];
result.push(temp)
}
}
return Math.max(...result)
};

实现2

可以对上面的方法进行优化,没有必要将所有的子串都保存起来,在计算过程中就可以实时的比较当前的最大值,最终返回的也是这个最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
const getMax = arr => {
console.time('getMax');
let max = arr[0];
let temp;
for (let i = 0; i < arr.length; i++) {
temp = 0;
for (let j = i; j < arr.length; j++) {
temp += arr[j];
max = Math.max(max, temp)
}
}
return max
};

这种解法的时间复杂度为O(n²)

实现3

实际上这是一道动态规划题目,以我对动态规划浅显的理解,就是从已有的状态中,推测下一状态的最优解。

要计算最优解,我们假设计算到的序列是i,这之前的子串和是temp,同时保存一个临时变量result,将tempresult每一步遍历都进行比较,保证result存的永远是当前结果的最大值。

如果temp小于0, 那么就抛弃temp,从i开始重新计算。

这样实际上只保留了计算过程中最近一步的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const getMax = arr => {
console.time('getMax');
let temp = 0;
let max = arr[0];
for (let i = 0; i < arr.length; i++) {
// 如果前面计算的子串和<0,那么就不要了
if (temp < 0) {
temp = 0
}
temp += arr[i];
// 上面可以简化为
// Math.max(0, tempMax) + arr[i]

max = Math.max(max, temp)
}
return max
};

这种解法的时间复杂度为O(n)

今天重新做,优化了一下,感觉更好理解一点(2019.01.25):

1
2
3
4
5
6
7
8
9
10
11
12
13
const getMax = arr => {
let result = 0;
let temp = 0;
for (let i = 0; i < arr.length; i++) {
temp += arr[i];
if (temp < 0) {
temp = 0
}
// 保证永远是当前结果的最大值
result = Math.max(temp, result);
}
return result
};

实现4

还可以用分治法来解决这个问题,连续最大子序列出现的位置有三种可能:

  1. 数组的左半部分MaxL
  2. 数组的右半部分MaxR
  3. 横跨数组左右两个部分MaxM

我们要做的就是分别求出上面三个值,然后取最大值就可以了,所以有:

1
const reuslt = Max.max(MaxL, MaxR, MaxM)

那么现在的关键就是分别取得这三个值了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const getMax = (arr, start = 0, end = arr.length - 1) => {
if (start > end) {
return 0
} else if (start === end) {
return arr[start]
}
// 取中间位置
let middle = Math.floor((start + end) / 2);
// 求横跨左右的最大连续子序列中左半部分的最大值
let maxMiddleL = arr[middle];
let tempL = 0;
for (let i = middle; i >= start; i--) {
tempL += arr[i];
maxMiddleL = Math.max(tempL, maxMiddleL)
}
// 求横跨左右的最大连续子序列中右半部分的最大值
let maxMiddleR = arr[middle + 1];
let tempR = 0;
for (let i = middle + 1; i <= end; i++) {
tempR += arr[i];
maxMiddleR = Math.max(tempR, maxMiddleR)
}
// 获得横跨左右的最大连续子序列和
const maxM = maxMiddleL + maxMiddleR;
// 获得位于数组左半部分的最大连续子序列和
const maxL = getMax(arr, start, middle);
// 获得位于数组右半部分的最大连续子序列和
const maxR = getMax(arr, middle + 1, end);
// 返回三者最大值
return Math.max(maxM, maxL, maxR)
};

这种解法的时间复杂度为O(nlgn)

我现在对于分治法的思想理解起来还是由一些困难,感觉数组排序中的归并排序也是利用了分治法的思想

算法还是要加强啊,唉

实现5:动态规划

2019.08.11更新

学习《算法图解》,学习了动态规划的算法,动态规划算法的关键就是将大的问题分解为子问题,使用子问题的答案来解决大问题。

对于连续子串最大和,可以分解为:

1
当前子串的值 = 当前值 + 之前子串的值

每个动态规划都会涉及一个表格,关键的点就是找到表格的值的计算方法,表格的行坐标是数组的各项的值j,列坐标是子串的长度i,每个单元格的值cell[i][j]就是长度为i的子串,以当前数字结束时,子串的和。

计算第一行的数据,代表的意思就是,当子串长度为1时,子串的值是-23,其他的单元格同理,这样就可以得到这一行的值。并且这一行最大的值就是17

到了第二行,第一个格子是不存在的,因为-23是不能构成长度为2的子串的。实际上表格中分割线以下的位置都是不存在的。

计算下一个格子的时候,就要利用上面的公式,当前值是17,子串长度为2,这个子串的和就等于17加上之前子串的值,之前子串的值就是cell[i-1][j-1],所以单元格的值就是17 + -23 = -6。,也就是说,长度为2、以17结束的子串即-23, 17这个子串的和是-6

这样就可以得到这一行的最大值是10,它比17小,所以单元格的最大值仍是17

同理可以填完整个表格:

填完之后发现,当前子串的最大值就是21,成员是17, -7, 11

用代码来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 连续子串最大和
const maxSubSum = arr => {
let result = 0;
const cell = [];

for (let i = 0; i < arr.length; i++) {
cell[i] = [];
for (let j = i; j < arr.length; j++) {
cell[i][j] = arr[j] + ((cell[i-1] && cell[i-1][j-1]) ? cell[i-1][j-1] : 0);
result = Math.max(result, cell[i][j])
}
}

return result;
};

虽然不一定更简单,但是是有理论依据的思想,有分析问题、建模、代码实现这样一个正确的解决问题的过程。

参考

哆啦斯基周 wechat
我的公众号,看心情更新,欢迎订阅!