使用快读不超时
最大子段和 考虑dp dp[i] = max(dp[i - 1] + a[i], a[i])
即,要不从上一段拼接过来,要么另起新的一段
import java.util.Arrays;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int n;
static int[] a;
static boolean res;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
a = new int[n];
for(int i = 0;i < n;i ++) {
a[i]= scan.nextInt();
if(a[i] >=0) res = true;
}
//System.out.println(Arrays.toString(a));
int start = 0,end = 0,sum = 0,st = 0,max = Integer.MIN_VALUE;
for(int i = 0;i<n;i++) {
sum += a[i];
if(sum > max) {
max = sum;
end = i;
start = st;
}
if(sum < 0) {
st = i + 1;
sum = 0;
}
}
if(res){
System.out.println( max + " "+ a[start] + " " + a[end] + " " );
}else{
System.out.println( 0 + " "+ a[0] + " " + a[n - 1] + " " );
}
}
}
import java.util.Arrays;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int n;
static int[] a;
static boolean res;
static int[] dp;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
a = new int[n + 1];
dp = new int[n + 1];
for(int i = 1;i <= n;i ++) {
a[i]= scan.nextInt();
if(a[i] >=0) res = true;
}
//System.out.println(Arrays.toString(a));
int start = 1,end = 1,sum = 0,st = 1,max = Integer.MIN_VALUE;
for(int i = 1;i<=n;i++) {
dp[i] = Math.max(dp[i - 1] + a[i], a[i]);
if(dp[i - 1] < 0) st = i ;
if(dp[i] > max) {
max = dp[i];
end = i;
start = st;
}
}
if(res){
System.out.println( max + " "+ a[start] + " " + a[end] + " " );
}else{
System.out.println( 0 + " "+ a[0] + " " + a[n - 1] + " " );
}
}
}