前端练习10 连续子串最大和
求连续子串最大和的练习。
题目
输入一组整数,例如:[-23, 17, -7, 11, -2, 1, -34, 2, -21, 9, 12]
,求出子序列的最大和
实现1
先尝试一种最暴力的方法,求最大子串,那么就将所有的子串计算出来,然后从中选出最大的
1 | const getMax = arr => { |
实现2
可以对上面的方法进行优化,没有必要将所有的子串都保存起来,在计算过程中就可以实时的比较当前的最大值,最终返回的也是这个最大值
1 | const getMax = arr => { |
这种解法的时间复杂度为O(n²)
实现3
实际上这是一道动态规划题目,以我对动态规划浅显的理解,就是从已有的状态中,推测下一状态的最优解。
要计算最优解,我们假设计算到的序列是i
,这之前的子串和是temp
,同时保存一个临时变量result
,将temp
和result
每一步遍历都进行比较,保证result
存的永远是当前结果的最大值。
如果temp
小于0
, 那么就抛弃temp
,从i
开始重新计算。
这样实际上只保留了计算过程中最近一步的状态
1 | const getMax = arr => { |
这种解法的时间复杂度为O(n)
今天重新做,优化了一下,感觉更好理解一点(2019.01.25):
1 | const getMax = arr => { |
实现4
还可以用分治法来解决这个问题,连续最大子序列出现的位置有三种可能:
- 数组的左半部分
MaxL
- 数组的右半部分
MaxR
- 横跨数组左右两个部分
MaxM
我们要做的就是分别求出上面三个值,然后取最大值就可以了,所以有:
1 | const reuslt = Max.max(MaxL, MaxR, MaxM) |
那么现在的关键就是分别取得这三个值了:
1 | const getMax = (arr, start = 0, end = arr.length - 1) => { |
这种解法的时间复杂度为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 | // 连续子串最大和 |
虽然不一定更简单,但是是有理论依据的思想,有分析问题、建模、代码实现这样一个正确的解决问题的过程。