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

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

   例如：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[];

  For i=（0 to n)

      Sum=0;

     For j=(i to n);

        Sum=sum+a[j];

       If(sum>max)

            Max=sum;

       具体实现代码：

package com.su.test;
public class Hellosu {
    public static void main(String[] args)
    {
      int a[]={-1,-2,5,-3};    //测试用例
      int length=a.length;
      int max=a[0];
      for(int i=0;i<length;i++)
      {
          int sum=0;               //每次赋值一层的第一个数
          for(int j=i;j<length;j++)
          {
              sum=sum+a[j];             //为后面连续数相加
              if(sum>max)
              {
                  max=sum;              //最大则存储在Max中
              }
          }
      }
      System.out.println(max);  
    }
 }

View Code 

 测试用例：

          int a[]={9,-3,4,-5,0};   测试结果：

          int a[]={-4,-5,-10,7,4,-12,19,0,-4,-6};  测试结果：

   算法分析：

         第一个循环内部的语句需要执行N次，而每次执行外部循环时，第二个循环内的语句至多执行N次，所以总的运行时间为O（n*n),而并没有达到老师所要求的水平，即O(n),

   可以考虑到如果检测所有的那些值的话，算法至少花费二次方的的时间。所以引出来是否可以有一个更好的方法能更有效地得出结果？

       第二种方法：即利用动态规划解决问题

   令cur(i)表示数组下标以i为起点的最大连 续下标最大的和，而max(i)表示前i个元素的最大子数组之和。那么我们就可以推出下一个max(i+1)应该为cur(i+1)和max(i)中选取一个最大值。递推式为：
          cur(i) = max{A[i],cur(i-1)+A[i]};
          max(i) = max{max(i-1),cur(i+1)};

     伪代码：

int max(int a[],int n) { 

    cur = a[0]; 
    max = a[0];
    for i=1 to n-1 do
        if cur<0 do 
            cur = 0;
        cur += a[i]; 
        if cur>max do
            max = cur; 
    return max; 
}

   源代码：

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);
   }
}

View Code

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

一个简单算法的设计（一个数组中连续区间和的最大值）,布布扣,bubuko.com

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

原文：http://www.cnblogs.com/sulindong/p/3591847.html