输入一个整形数组，数组里有正数也有负数。

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

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

注：时间复杂度是关键要求。

1 package shuzu; 2  3 import java.util.Scanner; 4  5 public class main { 6     public static void main(String[] args) { 7         int n; 8         int maxsum = 0; 9         int maxstart = 0;//用于判断子数组是否小于010         Scanner in = new Scanner(System.in);11         System.out.println("输入数组的长度");12         n = in.nextInt();13         int num[]=new int[n];14         System.out.println("输入数组中的值");15         for(int i = 0;i < n;i++)16         {17             num[i] = in.nextInt();18         }19         maxsum = num[0];20         for(int i = 0;i < n;i++)21         {22             if (maxstart <= 0) {23                 maxstart = num[i];24             }else {25                 maxstart += num[i];26             }27             28             if (maxsum < maxstart) {29                 maxsum = maxstart;30             }31         }32         System.out.println("最大值为：" + maxsum);33     }34 }