C++算法练习day70——53.最大子序和

题目来源：. - 力扣（LeetCode）

题目思路分析

题目：寻找最大子数组和（也称为最大子序和）。

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

思路：

1. 暴力解法：最直接的方法是遍历所有可能的子数组，并计算它们的和，然后找出其中的最大值。然而，这种方法的时间复杂度是 O(n^3)，对于大型数组来说效率太低。

2. 动态规划：我们可以使用动态规划来优化这个问题。定义一个变量 maxnums 来记录当前找到的最大子数组和，另一个变量 pos 来记录当前子数组的和（以当前元素为结尾）。遍历数组时，对于每个元素，我们有两种选择：要么将其加入当前的子数组（即 pos + nums[i]），要么开始一个新的子数组（即 nums[i]）。然后，更新 maxnums 为 maxnums 和 pos 中的较大值。

3. Kadane's Algorithm：上述动态规划方法实际上就是著名的 Kadane's Algorithm。它的核心思想是，在遍历数组时，不断更新以当前元素为结尾的最大子数组和，同时记录全局的最大子数组和。

代码:

#include <vector>  
#include <algorithm> // 为了使用 max 函数  class Solution {  
public:  int maxSubArray(vector<int>& nums) {  // 初始化最大子数组和为数组的第一个元素  int maxnums = nums[0];  // 初始化当前子数组和为数组的第一个元素  int pos = nums[0];  // 遍历数组（从第二个元素开始）  for (int i = 1; i < nums.size(); i++) {  // 更新当前子数组和：要么继续当前子数组，要么开始新的子数组  pos = max(pos + nums[i], nums[i]);  // 更新全局最大子数组和  maxnums = max(maxnums, pos);  }  // 返回全局最大子数组和  return maxnums;  }  
};

知识点摘要

1. Kadane's Algorithm：一种用于解决最大子数组和问题的线性时间复杂度算法。
2. 动态规划：一种通过将问题分解为更小的子问题来解决问题的方法，通常用于优化问题。
3. max 函数：用于比较两个值并返回其中的较大值。

本文介绍了如何使用 Kadane's Algorithm 来解决最大子数组和问题。通过维护两个变量（全局最大子数组和和当前子数组和），我们可以在遍历数组时不断更新它们，并最终得到全局最大子数组和。这种方法的时间复杂度是 O(n)，非常高效。希望本文能帮助大家更好地理解最大子数组和问题和 Kadane's Algorithm。