题目描述

给出一个长度为 nnn 的序列 aaa，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 nnn。

第二行有 nnn 个整数，第 iii 个整数表示序列的第 iii 个数字 aia_iai​。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

7
2 -4 3 -1 2 -4 3

输出 #1

4

说明/提示

样例 1 解释

选取 [3,5][3, 5][3,5] 子段 {3,−1,2}\{3, -1, 2\}{3,−1,2}，其和为 444。

数据规模与约定

• 对于 40%40\%40% 的数据，保证 n≤2×103n \leq 2 \times 10^3n≤2×103。
• 对于 100%100\%100% 的数据，保证 1≤n≤2×1051 \leq n \leq 2 \times 10^51≤n≤2×105，−104≤ai≤104-10^4 \leq a_i \leq 10^4−104≤ai​≤104。

• package LuoGu;import java.util.Scanner;/*** @author admin $* @title $* @description $* @updateTime $ 17:52$ $* @throws $*/
  public class P1115 {public static void main(String[] args) {Scanner scanner =new Scanner(System.in);int n=scanner.nextInt();int [] a=new int[n+1];for (int i = 0; i <n ; i++) {a[i]=scanner.nextInt();}System.out.println(maxSum(a.length,a));}private static int maxSum(int n, int[] array) {int sum = 0, b = 0;  // 定义中间值bfor (int i = 0; i < n; i++) {if (b > 0)       // 实现上述的动态规划递归式b += array[i];elseb = array[i];if (b > sum)   // 更新结果sum = b;}return sum; // 返回结果}}