结对开发——求环形一维数组最大子数组的和

题目:返回一个整数数组中最大子数组的和。
要求：
（1）输入一个整形数组，数组里有正数也有负数。
（2）数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
（3）如果数组A[0]……A[j-1]首尾相邻，允许A[i-1]， …… A[n-1]， A[0]……A[j-1]之和最大。
（4）同时返回最大子数组的位置。
（5）求所有子数组的和的最大值。要求时间复杂度为O(n)。
一、设计思想
这个问题的最优解一定是以下两种可能。
可能一：最优解没有跨过array[n-1]到array[0]，即和非环形数组一样了。
可能二：最优解跨过array[n-1]到array[0]，新问题。
对于第一种情况，我们可以按照非环形数组求法来求，为max1；对于第二种情况，可以将原问题转化为数组的最小子数组和问题，再用数组全部元素的和减去最小子数组和，那么结果一定是跨过a[n-1]到a[0]情况中最大的子数组和，设为max2。最终结果即为max1与max2中较大的那个。
例1：有数组5、-1、-6、8、2
求得max1=10，max2=15，则取较大的max2作为结果。
例2：有数组-6、8、1、6、-1
求得max1=15，max2=14，则取较大的max1作为结果。

二、源程序

package com.minirisoft;
import java.util.*;
public class MaxArray {
    public static void main(String[] args)
    {
        int o1=0;
        int num,i;
        int sum=0;
        int max;
        int first=0;
        int last=0;
        int order=0;
        Scanner cin=new Scanner(System.in);
        System.out.print("请输入数组的长度：");
        num=cin.nextInt();
        int array[]=new int[num];
        int max1=array[0];
        int min=array[0];
        for(i=0;i<num;i++)
        {
            array[i]=cin.nextInt();
        }
        for(i=0;i<num;i++)
        {
             if(sum<=0)
             {
                 sum=array[i];
                 first=i;
             }
             else
             {
                 sum=sum+array[i];
             }
             if(sum>max1)
             {
                 max1=sum;
                 last=i;
             }
        }
        System.out.println("第一种情况的最大值："+max1);
        for(i=0;i<num;i++)
        {
             if(sum>=0)
             {
                 sum=array[i];
                 o1=i;
             }
             else
             {
                 sum=sum+array[i];
               
             }
             if(sum<min)
             {
                 min=sum;
                 order=i;
             }
        }
        int sum1=0;
        for(i=0;i<num;i++)
        {
            sum1=sum1+array[i];
        }
        int max2=sum1-min;
        System.out.println("第二种情况的最大值："+max2);
        if(max1>max2)
        {
            System.out.println("和最大子数组为：");
            max=max1;
            for(int j=first;j<=last;j++){
                System.out.println(array[j]+"	");
            }
        }
        else
        {
            max=max2;
            System.out.println("和最大子数组为：");
            for(int j=0;j<num;j++){    
                if(j<o1||j>order){
                    System.out.println(array[j]+"	");
                }
                /*if(j!=order)
                {
                    System.out.print(array[j]+"	");
                }*/
            }
        }
        
        System.out.println("子数组和的最大值为："+max);
        
    }

}

三、运行结果截图：

四、心得体会

首先是设计思路，一开始我们在课上和同学们想的也都差不多，就是单纯求最大子数组的和，后来我们在写程序过程中，时间复杂度不符合要求，新增了一种思路，即求“sum - 最小子数组和“。两种情况的最大字数组的和都和之前那种非环形的数组求和思路一样，实现起来比重构数组神马的简单些.

结对开发——求环形一维数组最大子数组的和

相关推荐