连续子数组的最大和

[编程题]连续子数组的最大和

热度指数：656633 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围:

$1 <= n <= 2\times10^5$

$-100 <= a[i] <= 100$

要求:时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$

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

示例1

输入

[1,-2,3,10,-4,7,2,-5]

输出

说明

经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2

输入

[2]

输出

示例3

输入

[-10]

输出

-10

算法知识视频讲解

推荐

信念哥

public class Solution {
     public int FindGreatestSumOfSubArray(int[] array) {
         if (array.length==0 || array==null) {
             return 0;
         }
         int curSum=0;
         int greatestSum=0x80000000;
         for (int i = 0; i < array.length; i++) {
             if (curSum<=0) {
                 curSum=array[i]; //记录当前最大值
             }else {
                 curSum+=array[i]; //当array[i]为正数时，加上之前的最大值并更新最大值。
             }
             if (curSum>greatestSum) {
                 greatestSum=curSum; 
             }
         }
         return greatestSum;
     }
 }

编辑于 2015-07-26 20:51:19 回复(100)