软件工程结对开发——返回一个整数数组中最大子数组的和（JAVA）

题目:返回一个整数数组中最大子数组的和。

要求： 输入一个整型数组，数组里有正数也有负数；

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和；

求所有子数组的和的最大值。要求时间复杂度为O(n)；

一、设计思想

1.首先随机产生一个数组，数组长度可自行输入，该数组里有正数也有负数。

2.从数组中第一个元素a[0]开始，依次计算a[0]、a[0]+a[1]、a[0]+a[1]+...+a[i]的值，即从a[0]开始的每个子数组的和，取出最大值。

3.再从数组第二个元素a[1]开始，依次往后计算每个子数组的和，取出最大值。

4.依次循环，循环num次，直到数组最后一个元素，将每次求得的最大值存到一个数组list[]中。

5.比较每次得出的子数组的和的最大值，再得出最大值。

二、源程序

 //作者：王雪青   陆宇

 //日期：2015年3月18日

 package com.java.lianxi;

 import java.util.*;

 public class lianxi2

 {

     public static void main(String[] args)

     {

         Scanner input=new Scanner(System.in);

         System.out.print("请输入数组中数的个数：");

         int num=input.nextInt();

         int array[]=new int[num];

         for(int i=0;i<num;i++)

         {

             if((int)(Math.random()*2)==0)

             {

                 array[i]=(int)(Math.random()*10);

             }

             else

             {

                 array[i]=-(int)(Math.random()*10);

             }

         }

         for(int i=0;i<num;i++)

         {

             System.out.println(array[i]);

         }

         int max=0;

         int list[]=new int[num];

         for(int j=0;j<num;j++)

         {

             max=array[j];

             int sum=0;

             for(int t=j;t<num;t++)

             {

                 sum=sum+array[t];

                 if(sum>max)

                 {

                     max=sum;

                 }

             }

             list[j]=max;

         }

         for(int i=0;i<num;i++)

         {

             System.out.print("第"+(i+1)+"次比较的子数组的和的最大值为：");

             System.out.println(list[i]);

         }

         for(int i=1;i<num;i++)

         {

             max=list[0];

             if(list[i]>max)

             {

                 max=list[i];

             }

         }

         System.out.print("子数组和的最大值为："+max);

     }

 }
     

三、运行结果截图：

四、心得体会和总结

　　我们组的两个人是我王雪青和陆宇，这个题目的实现方法是陆宇想到的，然后程序是由我编写的，程序中的问题是我们两个一起解决的。这个程序基本实现了题目中的要求，但是时间复杂度不满足要求，今后我们会对这方面做改进，使程序更加完善。

软件工程结对开发——返回一个整数数组中最大子数组的和（JAVA）的相关教程结束。