首页 > 编程语言 > 详细

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

时间:2015-09-16 17:23:25      阅读:133      评论:0      收藏:0      [点我收藏+]

【题目描述】

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

要求时间复杂度为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         }

 

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

原文:http://www.cnblogs.com/HuoAA/p/4813559.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!