1、题目：求一个数组的最大线性子数组
2、常规求法
这个方法相信大家都会想到，但是这个方法比较复杂，想法很简单，思路是：两层for循环遍历，从第一个元素开始一直累加后面的元素，找到最大的值赋给maxNum。
这个方法的时间复杂度是O(n2)，
3、第二种方法就是动态规划，这个名字不太清楚，思路是：遍历这个数组，从第一个元素开始向后加，这个值为curNum，当这个curNum的值小于0的时候就不会再加了（因为curNum是负数的话，加后面的数就会比前面的数小，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和），当这个值curNum比最大值maxNum大的时候就把curNum赋给maxNum。
这个方法的时间复杂度是O(n),代码如下：
1 /** 2 * 求一个数组的最大线性子数组 3 * @author lixiaochao 4 * 5 */ 6 public class MaxArray { 7 8 public static void main(String[] args) { 9 int[] a = new int[]{2,4,-7,5,2,-1,2,-4,3}; 10 int curSum = 0; //中间态的值 11 int maxSum = 0; //这个数组的最大值 12 int start= 1; //起始位置 13 int end = 0; //末位置 14 for(int i =0; i < a.length; i++){ 15 curSum += a[i]; 16 if(maxSum < curSum){ 17 maxSum = curSum; 18 end = i+1; 19 } 20 System.out.println("curSum= "+curSum+", a[i]= "+a[i]+",start="+start); 21 /* 22 * 当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数， 23 * 那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和 24 */ 25 if(curSum < 0){ 26 curSum = 0; 27 start = i+2; 28 } 29 } 30 System.out.println("最大值为："+maxSum); 31 System.out.println("开始位置为："+start+",结束位置: "+end); 32 33 } 34 35 }
以上是个人观点，有什么不对的地方，还请大家指正，
原文：http://www.cnblogs.com/lixiaochao/p/5666522.html