#yyds干货盘点# 名企真题专题: 连续最大和

时间:2022-12-04 23:01:01

1.简述:

描述

一个数组有 N 个元素,求连续子数组的最大和。 例如:[-1,2,1],和最大的连续子数组为[2,1],其和为 3

输入描述:

输入为两行。 第一行一个整数n(1 <= n <= 100000),表示一共有n个元素 第二行为n个数,即每个元素,每个整数都在32位int范围内。以空格分隔。

输出描述:

所有连续子数组中和最大的值。

示例1

输入:

3
-1 2 1

输出:

3

2.代码实现:

import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sums=0, maxsums=Integer.MIN_VALUE; //考虑全为负数的情况
for(int i=0;i<n;i++){
sums+=sc.nextInt();
maxsums=Math.max(maxsums,sums);
sums= sums<0?0:sums; //代码核心了,如果当前求和为负,则抛弃之前的连续数组,重新开始求和

}
System.out.println(maxsums);
}
}