【个人作业】数组

雨点打透心脏的1/2处 2022-01-07 04:05 213阅读 0赞

要求：

返回一个整形数组，数组里有正数也有负数

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

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 package 个人作业1;
     2 
     3 import java.util.Scanner;
     4 
     5 public class Main {
     6     public static void main(String[] args)
     7     {
     8         int LONG=20;                    //数量
     9         int range=LONG/2;                    //-n ~ +n
    10         int i=0,t=0;
    11         Scanner input=new Scanner(System.in);
    12         int [] num=new int[LONG];
    13         int [] kuai=new int[LONG];
    14         int sum=0,max=0,aMax=num[0];
    15         for(int k=0; k<LONG; k++)
    16         {
    17             num[k]=(int)(1+Math.random()*range*2)-range;
    18             System.out.print(num[k]+"   ");
    19         }
    20         System.out.println();
    21         System.out.println("——————————————————————————————————————");
    22         
    23         //从第一个开始加直到最大，中途记录
    24         for(i=0;i<num.length;i++)//起始
    25         {
    26             t=0;
    27             max=num[t];//赋初值
    28             for(sum=num[t+i];t<num.length-i-1;t++)//加
    29             {
    30                 if(max<=sum)//比较，记录最大
    31                 {
    32                     max=sum;
    33                     
    34                 }
    35                 sum=sum+num[t+1+i];
    36             }
    37             if(aMax<=max)
    38             {
    39                 aMax=max;
    40             }
    41             System.out.print(max+"   ");
    42             
    43         }
    44 
    45         System.out.println();
    46         System.out.println();
    47         System.out.println(aMax);
    48         
    49 
    50     }
    51 }

Main

转载于:https://www.cnblogs.com/gothic-death/p/10508192.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211227/214d6a7551794b5ab6b03ed6477d3f6d.png