leetcode hot100【LeetCode 53.最大子数组和】java实现

2025/9/23 22:05:37 来源：https://blog.csdn.net/qq_14815605/article/details/143904726 浏览: 次关键词：leetcode hot100【LeetCode 53.最大子数组和】java实现

LeetCode 53.最大子数组和

题目描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（至少一个元素），返回其最大和。
子数组是数组中的一个连续部分。

示例 1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

示例 2:

输入: nums = [1]
输出: 1

示例 3:

输入: nums = [5,4,-1,7,8]
输出: 23

Java 实现代码

public class Solution {public int maxSubArray(int[] nums) {int maxSum = nums[0];int currentSum = nums[0];for (int i = 1; i < nums.length; i++) {currentSum = Math.max(nums[i], currentSum + nums[i]);maxSum = Math.max(maxSum, currentSum);}return maxSum;}
}

解题思路

这道题可以使用动态规划来解决。核心思路是利用一个数组 dp 来存储以每个位置 i 结尾的最大子数组和。

1.状态定义： dp[i] 表示以 nums[i] 结尾的最大子数组和。

2.状态转移方程：

如果 dp[i-1] > 0，则 dp[i] = dp[i-1] + nums[i]。
如果 dp[i-1] <= 0，则 dp[i] = nums[i]。

3.优化：由于 dp[i] 只依赖于 dp[i-1]，可以用一个变量 currentSum 来代替 dp 数组，从而将空间复杂度优化为 O(1)。