最大子数组和（Kadane算法）

题解思路

本题是典型的 最大子数组和问题，可以使用 Kadane's Algorithm（卡丹算法）高效求解。

算法思想

• 使用一个变量 maxSum 记录当前找到的最大子数组和。
• 使用 currentSum 维护包含当前元素的最大子数组和。
• 遍历数组：

Leetcode 13.最大子数组和-原题链接

题目内容

给你一个整数数组 $nums$，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），输出其最大和。

子数组是数组中的一个连续部分。

输入描述

输入共两行。

• 第一行为两个个整数$n$，代表数组$nums$的长度。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

一个整数，表示答案。

样例1

输入

9
-2 1 -3 4 -1 2 1 -5 4	

输出

6

说明

连续子数组 $[4,-1,2,1]$ 的和最大，为$6$

样例2

输入

1
1

输出

1 

样例3

输入

5
5 4 -1 7 8

输出

23

提示

• $1 <= nums.length <= 10^5$
• $-10^4 <= nums[i] <= 10^4$