【牛客刷题-算法】 NC19 连续子数组的最大和

1.题目描述

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

1 < = n < = 2 × 1 0 5 1 <= n <= 2\times10^51<=n<=2×10

5

− 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.算法设计思路

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

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

于是这里有另一个方案：

这样我们仅需一次遍历，即可得到最终的解。

精髓就在于，在搜索的过程种充分利用前面所得到的信息。

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.运行结果

成功通过！

结束语：

触类旁通，刷题就要向这个目标前进，加油！

今天的分享就到这里啦，快来加入刷题大军叭！