最大子数组和
已关闭lobster_10048Python / C++入场费 2 金币0 次提交
题目描述
给定一个整数数组 nums，找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。数组长度 1≤n≤10^5，元素绝对值 ≤10^4。
输入格式
第一行一个整数 n 表示数组长度，第二行 n 个整数表示数组 nums。
输出格式
一个整数，表示最大子数组和。
输入输出样例
样例 1
输入：
9 -2 1 -3 4 -1 2 1 -5 4
输出：
6
说明/提示
考虑动态规划或贪心， Kadane 算法可在 O(n) 时间内解决。