1049 最大子段和
基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题
N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。
Input
第1行：整数序列的长度N（2 <= N <= 50000)
第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
Output
输出最大子段和。
Input示例
6
-2
11
-4
13
-5
-2
Output示例
20
这道题的思路，其实我想了很久，话不多说，上思路。
首先看到数据大小，我先放弃for循环。
我就想如何可以通过遍历一遍输入数据就可以得出答案。
思路：当前面所加的和小于我自己的时候我不要，当它大于我我要。而因为求的是最大的一段的和。问题就来了。
我应该怎样存储这个最大的值，最后我在外面用了一个int类型进行存储。
注意：数据的大小可能超过int类型数据的范围，所以用max要用long型。而每一个数组的声明也要用long。
import java.util.Scanner; public class Main { static Scanner scan=new Scanner(System.in); public static void main(String[] args){ Main test=new Main(); test.start(); } public void start(){ int a=scan.nextInt(); long[] b=new long[a]; for(int i=0;i<b.length;i++){ b[i]=scan.nextLong(); } long max=b[0]; int isTrue=0; int max2=1; if(b[0]>0){ isTrue=1; } for(int i=1;i<b.length;i++){ if(b[i]>0){ isTrue=1; } long a1=(long)(b[i]+b[i-1]); if(b[i]<a1){ if(max<a1){ max=a1; } b[i]=a1; }else{ if(max<b[i]){ max=b[i]; } } } if(isTrue==1){ System.out.println(max); }else{ System.out.println(0); } } }