个人主页：清风莫追推荐一款好用的面试、刷题神器牛客网：👉点击加入刷题大军👈

@[toc]

1.题目描述

描述输入一个长度为 n 的整型数组 array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为 1。求所有子数组的和的最大值。数据范围:$1<=n<=2\times 10^5$$-100<=a[i]<=100$

要求: 时间复杂度为 O(n)O(n)，空间复杂度为 O(n)O(n)进阶: 时间复杂度为 O(n)O(n)，空间复杂度为 O(1)O(1)

2.算法设计思路

这题感觉与之前的一个题：买卖股票的最好时机 有共通之处。

首先我们要意识到，对于题中的输入数据规模，“枚举出所有的连续子数组，对它们分别求和，然后找到最大值”的方案是不可行的（因为该方案的时间开销随数据规模呈指数增长）。

于是这里有另一个方案：

• 第 i 个元素作为我们最终的子数组的末位元素时，将能得到的最大子数组和记为$ma{x}_i$
  

• 假设我们已经知道$ma{x}_i$的值，就可以很简单地求出$ma{x}_{i+1}$，即：$ma{x}_{i+1}=maxma{x}_i+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期参赛话题：学习笔记