【置顶】最大连续子数组
分类:
文章
•
2024-05-19 20:06:16
最大连续子数组
题目描述:
给定一个数组A[0,…,n-1],求A的连续子数组,使得该子数组的和最大。
例如 数组: 1, -2, 3, 10, -4, 7, 2, -5, 最大子数组:3, 10, -4, 7, 2
最大连续子数组的解法分析
暴力法、 分治法、分析法、动态规划法
1.暴力法分析:
直接求解A[i,…j]的值:
0≤ i < n, i≤ j < n, i,i+1…,j-1,j的最大长度为n,因此:时间复杂度O(n3)
2.分治法分析
将数组从中间分开,那么最大子数组要么完全在左半边数组,要么完全在右半边数组,要么跨立在分界点上。完全在左数组、右数组递归解决。跨立在分界点上:实际上是左数组的最大后缀和右数组的最大前缀的和。因此,从分界点向前扫,向后扫即可。
3.分析法(逻辑推理的算法应用)
前缀和p[i] = a[0] + a[1] + …+a[i] s[i,j]=p[j]-p[i-1](定义p[-1] = 0)
算法过程
1. 求i前缀p[i]: 遍历i:0≤i ≤n-1, p[i]=p[i-1]+A[i]
2. 计算p[i]-p[j]
遍历i:0≤i ≤n-1,求最小值m, m的初值取0(P[-1]=0),然后遍历p[0…i-1],更新m
p[i]-m即为以a[i]结尾的数组中最大的子数组
3. 在第2步中,可顺手记录p[i]-m的最大值。
为什么?
1、2步都是线性的,因此,时间复杂度O(n)。记S[i]为以A[i]结尾的数组中和最大的子数组
则:S[i+1] = max(S[i]+A[i+1], A[i+1]), S[0]=A[0], 遍历i: 0≤i ≤n-1
动态规划:最优子问题
时间复杂度:O(n)