XingHuiSamaの宝藏之地

给你一个整数数组 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

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

以前做过的题，我居然没想到用DP

首先是前缀和解题

前缀和

1. 核心思想

通过构建前缀和数组，将“求连续子数组的最大和”转换为“求两个前缀和的最大差值”。连续子数组的和可以表示为前缀和之差：Sums[i] - Sums[j]（其中 j < i）。为了使差值最大，在固定当前右端点 Sums[i] 时，需要减去其遍历历史中出现过的最小前缀和 minSum。

2. 逻辑拆解

N+1 哨兵数组构建：引入长度为 nums.size() + 1 的 Sums 数组，首位默认为 0。此设计有效处理了完整保留原数组前部元素的截取场景（即减去 Sums[0]），避免了复杂的边界判定。
第一次遍历（预处理）：顺序累加原数组元素，将各位置的前缀和依次存入 Sums 数组。
第二次遍历（计算极值）：
计算差值与更新上限：在每次循环中，优先计算 Sums[i] - minSum 并尝试更新全局最大值 maxSum。
更新历史下限：随后执行 Sums[i] < minSum 判断以更新历史最小前缀和。此严格的执行顺序保证了被减数必定在减数之后出现，从逻辑上排除了计算反向子数组的错误可能。

class 最大子数组和 {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int minSum = 0;
        vector<int> Sums = vector<int>(nums.size()+1, 0);
        int maxSum = INT_MIN;
        for (int i = 1;i < Sums.size();i++) {
            sum += nums[i-1];
            Sums[i] = sum;
        }

        for (int i = 1;i < Sums.size();i++) {
            if (Sums[i] - minSum > maxSum) {
                maxSum = Sums[i] - minSum;
            }
            if (Sums[i] < minSum) {
                minSum = Sums[i];
            }
        }

        return maxSum;
    }
};

3. 复杂度分析

时间复杂度：O(N)。分别执行了两次常数操作的一维数组遍历。
空间复杂度：O(N)。额外开辟了与输入数组规模相当的 Sums 数组。

贪心算法

1. 核心思想

贪心算法的核心在于“局部最优解的不断累加与及时止损”。在遍历数组的过程中，将当前元素之前的累加和视为一个“历史资产”。如果历史资产是正数，那么它对当前元素有增益效果，应该继续合并；如果历史资产变为负数或零，它就成了拖油瓶，此时果断抛弃过去的累加，以当前元素作为新的起点重新计算。

2. 逻辑拆解

极其稳妥的初始化：将局部变量 sum 和全局记录 maxSum 均初始化为数组的第一个元素 nums[0]，并让循环从索引 1 开始。这种设计完美覆盖了数组长度仅为 1 的边界情况，并确立了真实的比较基准。
贪心抉择（验资与入伙）：
if (sum > 0) 分支：前方的累加和为正，具备“投资价值”。将当前元素 nums[i] 并入团队，执行 sum += nums[i]，享受前方带来的正向红利。
else 分支：前方的累加和已跌至零或负数，沦为“负资产”。此时果断切割，执行 sum = nums[i]，让当前数字自立门户，成为新子数组的起点。
实时巅峰记录：无论是选择入伙还是单干，完成当前元素的抉择后，立刻执行 maxSum = max(sum, maxSum);。这保证了在 sum 跌入负数被清零重置之前，其曾经达到过的历史最高点已被永久封存。

class 最大子数组和 {
    //贪心算法求解
public:
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int maxSum = nums[0];
        for (int i = 1;i < nums.size();i++) {
            if (sum > 0) {
                sum += nums[i];
                maxSum = max(sum, maxSum);
            }
            else {
                sum = nums[i];
                maxSum = max(sum, maxSum);
            }
        }

        return maxSum;
    }
};

3. 复杂度分析

时间复杂度：O(N)。仅需对数组进行一次从左到右的线性遍历，没有嵌套循环，执行效率极高。
空间复杂度：O(1)。全程只维护了 sum 和 maxSum 两个整型变量，将内存消耗压榨到了极致的常数级别。

动态规划

1. 核心思想

动态规划的本质是“带记忆的递推推导”。通过定义极其严格的局部状态（dp[i] 代表必须以第 i 个元素结尾的连续子数组最大和），确保子数组在物理位置上的连续性。利用已经求出的历史最优状态 dp[i-1]，推导出当前状态 dp[i]。全局的最优解，就隐藏在这些所有局部最优状态的巅峰之中。

2. 逻辑拆解

状态定义与初始化：开辟一个与原数组同等规模的 dp 数组。将 dp[0] 毫无悬念地初始化为 nums[0]（因为以第一个数字结尾的子数组只能是它自己）。同时将全局记录 maxSum 也定调为 nums[0]。
状态转移方程 dp[i] = max(dp[i - 1] + nums[i], nums[i])：这是算法的灵魂。对于当前的 nums[i]，面临两条清晰的推导路径：
继承历史：如果前一个状态 dp[i - 1] 大于 0，说明前面的子数组能提供正向增益，于是顺理成章地将当前元素拼接上去（dp[i - 1] + nums[i]）。
另起炉灶：如果前一个状态 dp[i - 1] 小于等于 0，说明强行拼接只会拉低自身的数值，此时拒绝继承，让当前元素单独成为一个新子数组的起点（nums[i]）。
全局最优收集：dp 数组只能记录“以谁结尾最大”，并不代表最后一个算出来的就是全局最大。因此，每次计算出新的 dp[i] 后，立即用 maxSum = max(maxSum, dp[i]) 捕捉并更新全局的最高纪录。

class 最大子数组和 {
    //根据贪心算法来的动态规划
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        int maxSum = nums[0]; // 已修复极小值边界漏洞
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            maxSum = max(maxSum, dp[i]);
        }

        return maxSum;
    }
};

3.复杂度分析

时间复杂度：O(N)。严格按照顺序填写了一遍一维的 dp 数组，状态转移的过程是常数级别的时间消耗。
空间复杂度：O(N)。为了记录每一步的推导状态，额外申请了一个长度为 N 的 dp 数组（注：如果将 dp 数组优化掉，用单一变量滚动记录，本解法在物理形态上就会等价于前一版的贪心算法）。