题目描述#

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

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

解题思路#

1. 动态规划策略：
   • 定义 dp[i] 为以第 i 个元素结尾的最大子数组和
   • 状态转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])
2. 空间优化：
   • 使用滚动变量 currentMax 代替 dp 数组
   • 实时更新全局最大值 globalMax
3. 贪心思想：
   • 当前元素如果能使子数组和增大则保留
   • 否则从当前元素重新开始计算子数组
4. 边界处理：
   • 数组全负时返回最大负值
   • 空数组返回0或特定值

代码实现#

1
/**
2
 * @param {number[]} nums
3
 * @return {number}
4
 */
5
var maxSubArray = function (nums) {
6
    let current = 0;
7
    let maxSum = nums[0];
8
    for (const num of nums) {
9
        current = Math.max(num, current + num);
10
        maxSum = Math.max(maxSum, current);
11
    }
12
    return maxSum;
13
}

相似题目#

• 买卖股票的最佳时机
• 乘积最大子数组
• 数组的度
• [最长湍流子数组](https://leetcode.cn/problems/longest-turbulent-subarray/
• 拼接数组的最大分数
• 任意子数组和的绝对值的最大值
• 经过一次操作后的最大子数组和
• 最大波动的子字符串
• 统计得分小于 K 的子数组数目
• 数组中字符串的最大值
• 找到最大开销的子字符串
• K 件物品的最大和
• 最大好子数组和
• 删除所有值为某个元素后的最大子数组和