LeetCode 53. 最大子数组和：暴力枚举与动态规划

题目说明

题目描述：

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

示例：

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

---

解题思路

这是一道经典的动态规划入门题。关键要点在于：子数组必须连续，且我们要找到其最大和。

题目链接

LeetCode #53 最大子数组和

---

方法一：暴力枚举法（Brute Force）

思路

• 枚举所有可能的连续子数组 [i, j]
• 计算每个子数组的和，记录其中的最大值。

复杂度分析

• 时间复杂度：O(n²)（两层循环）
• 空间复杂度：O(1)

Java 实现

public class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (   i; j < nums.length; j++) {
                sum += nums[j];
                maxSum = Math.max(maxSum, sum);
            }
        }
         maxSum;
    }
}