NC19 连续子数组的最大和_给定一个长度为 n 的数组,数组中的数为整数。 请你选择一个非空连续子数组,

描述

给定一个长度为 n的数组，数组中的数为整数。

请你选择一个非空连续子数组，使该子数组所有数之和尽可能大。求这个最大值。

输入描述：

第一行为一个正整数 n，代表数组的长度。 1\leq n \leq10^51≤n≤105

第二行为 n个整数 a_iai​，用空格隔开，代表数组中的每一个数。 |a_i| \leq 10^9∣ai​∣≤109

输出描述：

连续子数组的最大之和。

示例1

输入：

3
3 -4 5

输出：

5

说明：

选择 [5] 这个子数组即可。
 

示例2

输入：

3
4 -3 5

输出：

6

说明：

选择 [4,-3,5] 这个子数组。
 

题目出自牛客网，大家可以自行去查看。

以下用的是java来完成

import java.util.*;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();//输入个数n
        long []arr=new long[n];//定义一个long型数组
        for(int i=0;i<n;i++){
            arr[i]=in.nextInt();//输入数组的值
        }
 long []dop=new long[n];//dop用来记录累加前面最大的值
        dop[0]=arr[0];
        for(int i=1;i<arr.length;i++){
            dop[i]=Math.max(dop[i-1]+arr[i],arr[i]);
        }
        Arrays.sort(dop);
        System.out.println(dop[n-1]);
 
    }
}