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)。
复杂度分析
- 时间复杂度: O(n)，其中
n是数组的长度。遍历数组一次即可完成计算。- 空间复杂度: O(1)，只使用了常量级的额外空间。