一维数组最大子数组

佚名 6年前 (2019-04-25) 随笔 1509人围观抢沙发百度已收录

程序思路：

首先实现求一维数组的最大子数组，然后实现打印输出计算步骤，在通过数组存储每一次打印输出的结果（包括最大值，最大子数组的首尾值），通过用户的要求回看步骤按要求输出输出数组的值。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码：

  1 package display;
  2 
  3 import java.util.Random;
  4 import java.util.Scanner;
  5 
  6 public class printout 
  7 {
  8     public static void main(String[] args) 
  9     {
 10          Scanner sc = new Scanner(System.in);
 11          Random random=new Random();
 12          System.out.print("输入数组的大小：");//获取用户要求的数组大小
 13          int p = sc.nextInt();
 14          int a[] = new int[p];//定义用户要求的数组大小
 15          System.out.print("输入数组内容（"+p+"个）：");
 16          for(int i = 0 ; i < p ; i++)//获取数组的值
 17          {
 18              a[i] = sc.nextInt();
 19              }
 20          System.out.print("\n");
 21          
 22          int sumshuzu = 0;//计算需检测的子数组的个数
 23          for(int i = 1; i <= p ;i++)
 24          {
 25              sumshuzu = sumshuzu + i;
 26          }
 27          
 28          int Max = a[0];//最大值
 29          int sumcha = 0;//记录已经检测的子数组的个数
 30          int n = 1 ;
 31          int Maxx = 1;//记录最大子数组的和的数组头的值
 32          int Maxy = 1;//记录最大子数组的和的数组尾的值
 33          int intMax[] = new int[sumshuzu];
 34          int intMaxx[] = new int[sumshuzu];
 35          int intMaxy[] = new int[sumshuzu];
 36          for(int m = 0 ; m < p ; m++)//计算子数组
 37          {
 38              int sum = a[m];//和
 39              sumcha = sumcha +1;
 40              System.out.println("共需检验"+sumshuzu+"个；"+"已检验"+sumcha+"个子数组");
 41              System.out.println("最大值是："+Max);
 42              intMax[sumcha-1] = Max;
 43              if(Max > sum)//如果子数组和小于最大值，则最大子数组不变，即Maxx和Maxy的值不变
 44              {
 45                  System.out.println("最大子数组值是从第"+Maxx+"个值加到第" +Maxy+"个值");
 46                  intMaxx[sumcha-1] = Maxx;
 47                  intMaxy[sumcha-1] = Maxy;
 48                  }
 49              if(Max < sum) //如果子数组和大于最大值，则最大子数组现在为一个数，即Maxx和Maxy的值相同
 50              {
 51                  Max = sum;
 52                  Maxx = m + 1;
 53                  Maxy = m + 1;
 54                  System.out.println("最大子数组值是从第"+Maxx+"个值加到第" +Maxy+"个值");
 55                  intMaxx[sumcha-1] = Maxx;
 56                  intMaxy[sumcha-1] = Maxy;
 57                  }
 58              for(n = m + 1;n < p ;n++ ) 
 59              {
 60                  if(Max < a[n]) Max = a[n];
 61                  sum = sum + a[n];
 62                  sumcha = sumcha +1;
 63                  System.out.println("共需检验"+sumshuzu+"个；"+"已检验"+sumcha+"个子数组");
 64                  System.out.println("最大子数组值是："+Max);
 65                  intMax[sumcha-1] = Max;
 66                  if(Max > sum)//如果子数组和小于最大值，则最大子数组不变，即Maxx和Maxy的值不变
 67                  {
 68                      System.out.println("最大子数组值是从第"+Maxx+"个值加到第" +Maxy+"个值");
 69                      intMaxx[sumcha-1] = Maxx;
 70                      intMaxy[sumcha-1] = Maxy;
 71                      }
 72                  if(Max < sum) //如果子数组和大于最大值，则最大子数组变化，即Maxx和Maxy的值变为此时计算的子数组的首和尾
 73                  {
 74                      Max = sum;
 75                      Maxx = m + 1;
 76                      Maxy = n + 1;
 77                      System.out.println("最大子数组值是从第"+Maxx+"个值加到第" +Maxy+"个值");
 78                      intMaxx[sumcha-1] = Maxx;
 79                      intMaxy[sumcha-1] = Maxy;
 80                      }
 81                  
 82                  }
 83              }
 84          System.out.println(" ");
 85          System.out.println("数组最大子数组值是："+Max);
 86          int k = 0;
 87          System.out.print("请输入是否回看步骤（回看回复1，不会看回复0）：");
 88          k = sc.nextInt();
 89          if( k == 1)
 90          {
 91              //回看计算步骤
 92              System.out.print("请输入要从第几步回看：");
 93              int huikan;
 94              huikan = sc.nextInt();
 95              System.out.println(" ");
 96              for(int i = huikan ;i < sumshuzu+1;i++)
 97              {
 98                  System.out.println("共需检验"+sumshuzu+"个；"+"已检验"+i+"个子数组");
 99                  System.out.println("最大值是："+intMax[i-1]);
100                  System.out.println("最大子数组值是从第"+intMaxx[i-1]+"个值加到第" +intMaxy[i-1]+"个值");
101                  }
102              }
103          }
104     }