连续子数组的最大和-腾讯笔试编程C/C++

题目：

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

数据范围:

1 <= n <= 10^5

-100 <= a[i] <= 100

（更多博文，欢迎来我的博客学习交流have_a_cat的博客_CSDN博客-PHP,Dcat-Admin框架,大厂热门笔试面试领域博主）

基础要求∣:时间复杂度为 O(n)，空间复杂度为 O(n)

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

示例

示例序号	输入	返回值	备注
示例1	[1,-2,3,10,-4,7,2,-5]	18	经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
示例2	[2]	2
示例3	[-10]	-10

分析：

以示例1为例分析本题

我们用一个变量sum，来计算目前得到的子数组的最大值。

我们用一个变量j，来计算当前子数组的和

步骤1(初始)★：

输入的数组array = [1,-2,3,10,-4,7,2,-5]

j = 0

sum = array[0] = 1

（更多博文，欢迎来我的博客学习交流have_a_cat的博客_CSDN博客-PHP,Dcat-Admin框架,大厂热门笔试面试领域博主）

步骤2★：

我们考虑array中的第零个值，array[0] = 1，

那么当前子数组的和 j = array[0] = 1

sum = j = 1;

步骤3★：

我们考虑array中的第一个值，array[1] = -2，

那么当前子数组的和 j = array[0] + array[1] = j(步骤2中的j) + array[1] = 1 + (-2) = -1，（哎呀，这时候发现了没？加上这个array[1]，子数组的和变成负的了，那还不如不加array[1]-->推出，最后想要的子数组，肯定不可能是array[0] + array[1]）因为j < 0 , 所以我们将j置为0

sum = 1(仍为步骤2中计算出的sum)

步骤4★：

我们考虑array中的第二个值，array[2] = 3，

那么当前子数组的和 j = array[2] = j(步骤3中的j) + array[2] = 0 + 3 = 3

因为3 > 1，即 j > sum , 所以sum =j= 3;

步骤5：

我们考虑array中的第三个值，array[3] = 10，

那么当前子数组的和 j = array[2] + array[3] = j(步骤4中的j) + array[3] = 3 + 10 = 13，

因为13 > 3，即 j > sum , 所以sum =j= 13;

步骤6：

我们考虑array中的第四个值，array[4] = -4，

那么当前子数组的和 j = array[2] + array[3] + array[4] = j(步骤5中的j) + array[4] = 13 + (-4) = 9，

sum = 13(仍为步骤5中计算出的sum)

步骤7：

我们考虑array中的第五个值，array[5] = -5，

那么当前子数组的和 j = array[2] + array[3] + array[4] + array[5] = j(步骤6中的j) + array[5] = 9 + 7 = 16，

因为16> 13，即 j > sum , 所以sum =j= 16;

（更多博文，欢迎来我的博客学习交流have_a_cat的博客_CSDN博客-PHP,Dcat-Admin框架,大厂热门笔试面试领域博主）

步骤8：

我们考虑array中的第六个值，array[6] = 2，

那么当前子数组的和 j = array[2] + array[3] + array[4] + array[5] + array[6]= j(步骤7中的j) + array[6] = 16 + 2 = 18，

因为18> 16，即 j > sum , 所以sum =j= 18;

步骤9：

我们考虑array中的第七个值，array[7] = -5，

那么当前子数组的和 j = array[2] + array[3] + array[4] + array[5] + array[6] + array[7] = j(步骤8中的j) + array[7] = 18 + (-5) = 13，

sum = 18(仍为步骤8中计算出的sum)

所以，最终sum的值为18

总结-编程思路

分析中的步骤	分析中的例子   -->	编程思路
步骤1(初始)	j = 0 sum = array[0] = 1	j = 0; sum = array[0];
步骤3	因为j < 0 , 所以我们将j置为0	if(j < 0){   j = 0; }
步骤4	j = array[2] = j(步骤3中的j) + array[2]	j = j + a[i];
步骤4	因为3 > 1，即 j > sum , 所以sum =j= 3;	if(j > sum){  sum =  j; }

C++代码

class Solution {

public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int i, j;
        int sum;
        if(array.size() > 0)
        {
            sum = array[0]; j = 0;
            for(i = 0; i < array.size(); i++)
            {
                j += array[i];
                if(j > sum){ sum = j;}
                if(j < 0){ j = 0;}
            }
        }
        return sum;
    }
};
           

（更多博文，欢迎来我的博客学习交流have_a_cat的博客_CSDN博客-PHP,Dcat-Admin框架,大厂热门笔试面试领域博主）

2021年即将结束，祝大家新的一年，继续写代码、爱代码、钻代码。

----2021年12月31日