1.题目描述
描述
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
数据范围:
1
<
=
n
<
=
2
×
1
0
5
1 <= n <= 2\times10^5
1<=n<=2×105
−
100
<
=
a
[
i
]
<
=
100
-100 <= a[i] <= 100
−100<=a[i]<=100
要求: 时间复杂度为 O(n)O(n)，空间复杂度为 O(n)O(n)
进阶: 时间复杂度为 O(n)O(n)，空间复杂度为 O(1)O(1)
2.算法设计思路
这题感觉与之前的一个题：买卖股票的最好时机 有共通之处。
首先我们要意识到，对于题中的输入数据规模，“枚举出所有的连续子数组，对它们分别求和，然后找到最大值”的方案是不可行的（因为该方案的时间开销随数据规模呈指数增长）。
于是这里有另一个方案：
- 第 i 个元素作为我们最终的子数组的末位元素时，将能得到的最大子数组和记为
m
a
x
i
max_i
maxi
- 假设我们已经知道
m
a
x
i
max_i
maxi的值，就可以很简单地求出
m
a
x
i
+
1
max_{i+1}
maxi+1，即：
m
a
x
i
+
1
=
m
a
x
{
m
a
x
i
+
a
[
i
]
,
a
[
i
]
}
max_{i+1} = max\{max_i+a[i],a[i]\}
maxi+1=max{maxi+a[i],a[i]}
这样我们仅需一次遍历，即可得到最终的解。
精髓就在于，在搜索的过程种充分利用前面所得到的信息。
3.算法实现
注：这里并不是完整代码，而只是核心代码的模式
/**
* @param array int整型一维数组
* @param arrayLen int array数组长度
* @return int整型
*/
int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
// write code here
int max_i = array[0];
int max_all = max_i;
for(int i = 1; i < arrayLen; i++){
if(max_i > 0)
max_i = array[i] + max_i;
else
max_i = array[i];
if(max_i > max_all)
max_all = max_i;
}
return max_all;
}
4.运行结果
成功通过！
结束语：
触类旁通，刷题就要向这个目标前进，加油！
今天的分享就到这里啦，快来加入刷题大军叭！
👉点击开始刷题学习👈
感谢阅读
个人主页：清风莫追
CSDN话题挑战赛第2期
参赛话题：学习笔记
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/114806.html
