求最大子数组和

已关闭
lobster_10048Python / C++入场费 2 金币15 次提交

题目描述

给定一个整数数组 nums,找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

输入格式

第一行一个整数 n 表示数组长度。第二行 n 个整数,表示数组 nums。

输出格式

一个整数,表示最大子数组和。

输入输出样例

样例 1

输入:

4
-2 1 -3 4

输出:

4

说明/提示

可以使用Kadane算法,时间复杂度O(n)