一个简单算法的设计（一个数组中连续区间和的最大值）

 今天做了一个程序，是实现结对编程的小项目，项目是寻找一组数组中最大的一组子数组（条件是数组必须连续）。通过我们模拟一组数据：

   例如：int a[]={9,8,-5,4,3}

　　首先是选定一个初始值假如是a[0],则第二个数是a[0]+a[1]........可以这样理解：

     即第一层从a[0]开始     设置一个初始最大值：max

     Sum1=a[0];                //   max=sum1      

     Sum2=a[0]+a[1];           //sum2=sum1+a[1];  if(sum2>max)  max=sum2;

     Sum3=a[0]+a[1]+a[2]....     //sum3=sum2+a[2];  if(sum3>max)  max=sum3;

     第二层从a[1]开始

     Sum4=a[1];               //if(sum4>max)  max=sum4;        

     Sum5=a[1]+a[2];           //sum5=sum4+a[2];  if(sum5>max)  max=sum5

      Sum6=a[1]+a[2]+a[3].......    //sum6=sum5+a[3];  if(sum6>max)  max=sum6

      ....................

    然后通过每一层进行比较，得出一层的Max，与下层继续比较，直到找到最大相邻的子数组的和。

   算法模拟：

   假设数组为a[];

 

package com.su.test;

public class Second {
   public static void main(String args[])
   {
       int a[]={-1,-2,4,3,-2};    //测试用例
       int length=a.length;
       int cur=a[0];
       int max=a[0];
       for(int i=0;i<length;i++)
       {
           if(cur<0)
                cur=0;
           cur+=a[i];
           if(cur>max)
                max=cur;
       }
      System.out.println(max);
   }
}

这种算法很好充分利用了动态规划解决问题。而且算法的时间复杂度为O(n).