跳到主要内容

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

提示：

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

第一次解​

不知道是不是贪心的贪心​

    int maxSubArray(vector<int>& nums) {
        int maxsum = 0;
        int sum = 0;
        for (int i: nums) {
            if (sum + i < 0) {
                sum = 0;
            } else sum += i;
            if(sum>maxsum)maxsum = sum;
        }
        if (maxsum == 0) {
            sort(nums.begin(), nums.end());
            return nums[nums.size()-1];
        }else
            return maxsum;
    }

2023/07/09 14:27:16

解答成功:

执行耗时:88 ms,击败了71.44% 的C++用户

内存消耗:66.1 MB,击败了66.38% 的C++用户

还能优化，下面的sort是因为我想不到更好的方法输出负数了，暂时

优化后逻辑有变，我先让sum+了前面一个先，然后此时不管是负数还是正数都能和输出的答案对比，这样就可以让答案有负数，最后再判断是不是负的，扔掉前面的

    int maxSubArray(vector<int>& nums) {
        int maxsum = INT32_MIN;
        int sum = 0;
        for (int i: nums) {
            sum += i;
            if(sum>maxsum)maxsum = sum;
            if(sum < 0) {
                sum = 0;
            }
        }
        return maxsum;
    }

2023/07/09 14:50:40

解答成功:

执行耗时:92 ms,击败了58.04% 的C++用户

内存消耗:66.1 MB,击败了88.64% 的C++用户

经典leetcode玄学，我把里面的排序一遍都比遍历里加if用的时间多

理论上我已经用dp写过一遍了，但是后来发现，之前算法课上用过分治

分治​

这道题类似于mergesort的分治，但是这要维护的东西比较多，思路很难学。

方法给你了，但是你知道他是怎么想出来这种结构的？思路历程是怎么样的？完全不知道。

很头疼

image-20220914085839291

我们有一种结构可以用来维护每次递归的区块，通过维护区块的这几个sum，合并之后就能得到最终解（建议搭配代码理解。

public class Info {
        public int total_Sum,lsum,rsum,msum;
        public Info(int total_Sum,int lsum,int rsum,int msum) {
            this.total_Sum=total_Sum;
            this.lsum=lsum;
            this.rsum=rsum;
            this.msum=msum;
        }
    }

    public int maxSubArray(int[] nums) {
            return Dc(nums,0, nums.length-1).msum;
    }

    public Info Dc(int[] nums, int l, int r) {
        if (l == r) {
            return new Info(nums[l], nums[l], nums[l], nums[l]);
        }

        Info l_Dc=Dc(nums,l,l+r>>1);
        Info r_Dc=Dc(nums,(l+r>>1)+1,r);
        return new Info(
                l_Dc.total_Sum + r_Dc.total_Sum,
                Math.max(l_Dc.lsum, l_Dc.total_Sum + r_Dc.lsum), //就是   5 2  3 4
                Math.max(r_Dc.rsum, r_Dc.total_Sum + l_Dc.rsum),
                Math.max(Math.max(l_Dc.msum, r_Dc.msum), r_Dc.lsum + l_Dc.rsum)

        );

现在我们希望能解出在[l,r]区间的最大连续子序列和msum，这个msum分三种情况

  1. 在[l,m]（就全在左边）
  2. 在[m,l]（全在右边）
  3. 横跨m，在左边界在左区间，右边界在右区间

只要将大问题分解完成小问题，将每个区块的左右区间都弄成最大，然后将最大的合并。

剩下的问题就是递归的实现还有每个小区间的左右sum和区间最大和msum的维护

关于totalsum，就是这个区间的的和

关于lsum，第一种就是不像右边扩张，不穿过m，

第二种就是像右边扩张，穿过m，即（l_Dc.totalsum+r_Dc.rsum)

image-20220914094533592

左右边都是对称的，目的是找出我们维护区间内的最大和，不管左还是右

关于msum 表示区间内的最大子段和，一般我们维护好l_sum或者r_sum就可以了，存在穿过m的情况，就将左右区间加起来。

dp​

class Solution {
//    public int maxSubArray(int[] nums) {
//      info
//      解答成功:
//      执行耗时:6 ms,击败了5.28% 的Java用户
//      内存消耗:50.4 MB,击败了60.26% 的Java用户
//      真垃圾啊,dp
//      int[] dp = new int[nums.length];
//      dp[0] = nums[0];
//      int max = dp[0];
//      for (int i = 1; i < nums.length; i++) {
//          if(dp[i - 1] > 0) {
//              dp[i] = dp[i - 1] + nums[i];
//          }else {
//              dp[i] = nums[i];
//          }
//      }
//      max= Arrays.stream(dp).max().getAsInt();
//      return max;

//      2.改进一点点,依然是dp
//      状态转移方程:
//      f(i)=max{f(i−1)+nums[i],nums[i]}1
//      采用for each循环加滚动数组的思想
//      info
//      解答成功:
//      执行耗时:1 ms,击败了100.00% 的Java用户
//      内存消耗:50.4 MB,击败了64.61% 的Java用户
//      int pre=0,maxAns=nums[0];
//      for(int x:nums){
//          pre=Math.max(pre+x,x);
//          maxAns=Math.max(maxAns,pre);
//      }
//      return maxAns;
//    }
}