转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4248609.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，故原出处已不好查到，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。下标为[2,6]。
若是时间复杂度为O(n^2),相信大家都容易解决，我用了双重循环的方法，类似于穷举法。但这里要求时间复杂度为O(n),则比较麻烦，在网上也找到不同的解决方案，其中，利用贪心算法的方式解决是相对简单的。
算法思想：
1)首先初始化子数组和的最大值max为最小负整数-(1<<31)，数组元素和sum为0,字数组的起始下标start=0和终止下标end=0。
2)从第一个元素开始循环遍历数组:
a.若相加后的sum为正，且sum>max，则max=sum；若sum<0，则sum=0。
b.否则，若sum<0，则sum=0。
算法的java实现：
1 package com.interview;
2 /**
3 *
4 * @author wjh
5 *
6 */
7 public class _3MaxArrSum {
8
9 /**
10 * @param args
11 */
12 public static void main(String[] args) {
13 int[] a = {7,-2,-2, -2, 3, 10};//{1, -2, 3, 10, -4, 7, 2, -5};
14 maxSum1(a);
15 //maxSum2(a);
16 }
17
18 //用二重循环 , 时间复杂度为O(n)
19 private static void maxSum1(int[] a){
20 int n = a.length;
21 int max= -(1<<31); //用来保存最大值，初始化为最小的整数
22 int sum = 0;
23 int start = 0; //开始下标
24 int end = 0; //结束下标
25 for(int i=0;i<n;i++){
26 int temp = sum; //保存上一次的sum
27 sum +=a[i];
28 //如果前面选中的子数组之和已经<=0,而a[i]>0,则前面部分已经可以抛弃了,start和end从新指向当前的i
29 if(temp==0&&sum>temp){ //若不求字数组的下标，则用不着这个分支
30 start=i;
31 end = i;
32 }
33 if(sum>0&&sum>max){ //设上一个正数为a[j],当a[i]>0,并且 a[i]+ a(j,i-1] 之间的<=0的数之和大于 0
34 max=sum;
35 end = i;
36 }
37 else if(sum<0){ //sum<0则将sum归0,若此处是else if,当形如{-2,2}的数据时第一次循环后max=sum=-2,
38 sum=0; //进入第二次循环时,temp=-2;sum=0; 不会进入第一个分支,start不动,进入第二个分支时max=0;下标和结果都错误
39 }
40 }
41 System.out.println("最大值为："+max);
42 System.out.println("取得最大值时数组的起始和终止下标为: ["+start+","+end+"]");
43 }
44 /** 里面的条件分支可改为：
45 * if(temp==0&&sum>temp){ //
46 start=i;
47 end = i;
48 }
49 if(sum>max){ //此时的sum肯定为正
50 max=sum;
51 end = i;
52 }
53 if(sum<0){ //
54 sum=0; //
55 }
56 */
57
58 //用二重循环 , 时间复杂度为O(n^2)
59 private static void maxSum2(int[] a){
60 int n = a.length;
61 int max= -(1<<31); //用来保存最大值，初始化为最小的整数
62 int start = 0; //开始下标
63 int end = 0; //结束下标
64 for(int i=0;i<n;i++){
65 int sum = 0;
66 for(int j=i;j<n;j++){
67 sum += a[j];
68 if(sum>max){
69 max = sum;
70 start = i;
71 end = j;
72 }
73 }
74 }
75 System.out.println("最大值为："+max);
76 System.out.println("取得最大值时数组的起始和终止下标为: ["+start+","+end+"]");
77 }
78 }
博主白杨的文章 http://xingyunbaijunwei.blog.163.com/blog/static/7653806720122273022366/ 给了我很大的帮助，在此致谢！