和最大子序列 蓝桥杯VIP试题 Java题解（这题坑多）
题目描述：
试题 算法提高 和最大子序列
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
对于一个给定的长度为N的整数序列A，它的“子序列”的定义是：A中非空的一段连续的元素（整数）。你要完成的任务是，在所有可能的子序列中，找到一个子序列，该子序列中所有元素的和是最大的（跟其他所有子序列相比）。程序要求你输出这个最大值。
输入格式
输入文件的第一行包含一个整数N，第二行包含N个整数，表示A。
其中
1 <= N <= 100000
-10000 <= A[i] <= 10000
输出格式
输出仅包含一个整数，表示你算出的答案。
样例输入
5
3 -2 3 -5 4
样例输出
4
思路： 求最大子序列问题，题设中说的是：“A中非空的一段连续的元素（整数）”
- 暴力解法，列出所有子序列，计算出结果，再做比较（时间复杂度太高，不推荐，本题测试数据是10万个，会timeout）
- 从头开始，使用一个临时变量来存储当前子序列的和，如果值小于等于0，就舍弃当前序列，重新开始，再使用一个变量来存储历史出现的最大值，最终输出这个变量就可以了
import java.util.Scanner;
/**
* 子数组连续累加和
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
//接受数据
for(int i=0;i<n;i++){
arr[i] = in.nextInt();
}
//处理数据
int max = arr[0];
//临时累加和
int tempMax = 0;
int q = 0;
//对数组进行处理
while(q<arr.length){
//谁大就变成谁
max = Math.max(tempMax,max);
tempMax += arr[q++];
//当当前累加和不能对后面累加做贡献时，舍弃
if(tempMax<=0)
tempMax = 0;
}
System.out.println(max);
}
}
能成功进行处理
但是如果你去提交代码，肯定会这样：
嗯？我们不妨把测试数据打开看看，再放到本地跑一下：
这数据，有点过分了，但是你以为这就是全部吗？
来看看本地运行结果：
具体原因是什么呢？我当时也很蒙蔽，又返回去看了一下题目条件，发现没有问题，值得范围是-10000~10000，没有超过int类型范围，然后我就去度娘上面查了一下这个InputMismatchException异常，发现是输入类型不匹配造成的异常，然后我把nextInt()换成next()试试：
arr[i] = Integer.parseInt(in.next());
然后就发现了一些奇怪的东西：
原来是把两个数据合在放在一起了，网上一些大佬说c++里面可以读取这种数据，我试了试c++,也不能，代码：希望大佬纠正一下：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n = 0;
cin>>n;
int *arr = new int[n];
int i = 0;
for(i=0;i<n;i++){
cin>>arr[i];
}
//处理数据
int maxVal = arr[0];
//临时累加和
int tempMax = 0;
int q = 0;
//对数组进行处理
while(q<n){
//谁大就变成谁
maxVal = max(tempMax,maxVal);
tempMax += arr[q++];
//当当前累加和不能对后面累加做贡献时，舍弃
if(tempMax<=0)
tempMax = 0;
}
cout<<maxVal<<endl;
return 0;
}
言归正传，回到Java中，我们可以这样过滤一下数据：
String next = in.next();
//负号不在第一位
if(next.lastIndexOf("-")>0){
//分割一下
String str1 = next.substring(0, next.lastIndexOf("-"));
arr[i++] = Integer.parseInt(str1);
String str2 = next.substring(next.lastIndexOf("-"));
arr[i] = Integer.parseInt(str2);
continue;
}
arr[i] = Integer.parseInt(next);
测试一下：
这次没错了，但是程序一直处于阻塞状态，盲猜两个正数放在一个了，导致输入的数没有10万个，in.next()导致程序阻塞，验证一下：
if(next.length()>6){
System.err.println(next);
return;
}
因为数据范围是-10000~10000所以最高只能有长度5，但是拼接过后就会超过这个长度
果然，有这些捣乱的数，因为int返回最大值数是2147483647，所以不会超限，这里我观察了一下运行的正确答案是33227197，正好就是那个最大的数，所以是不能再进行分割了（如果是为了AC），但是这道题最主要的是掌握求子序列最大和的方法，过于纠结这个测试数据就有点本末倒置了，所以，后面我们直接更改一下接收条件：
for(int i=0;i<n-1;i++)