【面试题31】连续子数组的最大和

【题目描述】

输入一个整型数组，数组里有正数，也有负数。数组中一个或连续的多个整数组成的一个子数组，求所有子数组的最大值。

要求时间复杂度为O(n)。

【解决方案】

解法一：举例分析数组的规律

我的代码实现，仅供参考：

 1         public static int FindGreatestSumOfSubArray(int[] arr)
 2         {
 3             if (arr == null || arr.Length < 1)
 4                 return -1;
 5 
 6             int max = arr[0];
 7             int prev = arr[0];
 8 
 9             for (int i = 1; i < arr.Length; i++)
10             {
11                 if (arr[i] + prev > arr[i])
12                 {
13                     prev += arr[i];
14                 }
15                 else
16                 {
17                     prev = arr[i];
18                 }
19 
20                 max = prev > max ? prev : max;
21             }
22 
23             return max;
24         }