牛客网系列--2017校招真题编程练习--滴滴出行--连续最大和

最新推荐文章于 2022-02-23 16:02:13 发布

zhangzhetaojj

最新推荐文章于 2022-02-23 16:02:13 发布

阅读量375

点赞数

分类专栏：牛客网笔试

本文链接：https://blog.csdn.net/zhangzhetaojj/article/details/80958348

版权

牛客网笔试专栏收录该内容

3 篇文章

订阅专栏

题目：

输入描述:

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

输出描述:

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

示例1

输入

复制

3 -1 2 1

输出

复制

解题思路：

动态规划，判断连续元素求和是否大于0，如果累计的和小于0，就从当前元素开始重新求和。

时间复杂度O(n)，空间复杂度O(1)。

代码实现：

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int res = Integer.MIN_VALUE;
        int sum = res;

        while (scanner.hasNextInt()) {
            int i = scanner.nextInt();
            sum = sum < 0 ? i : sum + i;
            res = Math.max(res, sum);
        }

        System.out.println(res);
    }
}