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)，只使用了常量级的额外空间。

原文地址：https://blog.csdn.net/qq_14815605/article/details/143904726

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！