前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每天一道leetcode-最大子序和

每天一道leetcode-最大子序和

作者头像
乔戈里
发布2019-01-09 15:27:21
5350
发布2019-01-09 15:27:21
举报
文章被收录于专栏:Java那些事

053_(最大子序和)Maximum Subarray

1 问题描述、输入输出与样例

1.1 问题描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

1.2 输入与输出

输入:

  • vector< int>& nums:给定的整数数组 nums

输出:

  • int:最大子序和

1.3 样例

1.3.1 样例1

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

2 思路描述与代码

2.1 思路描述(在线处理法)

其思想是如果当前累加的和 this_sum < 0,那么其肯定不会使得后续的子序和更大,所以累加值 this_sum 置 0 重新累加。

代码语言:javascript
复制
len_nums 为输入数组的长度
max_sum 为记录的最大和
this_sum 记录当前累加的结果
for( i = 0; i < len_nums; i++ ){
    this_sum += nums[i];
    max_sum = max(max_sum, this_sum);
    if(this_sum < 0) this_sum = 0;
}

2.2 代码

代码语言:javascript
复制
class Solution {
public:
    const int MIN = -2147483648;
    int maxSubArray(vector<int>& nums) {
        return maxSubArray_online_processing(nums);
    }
    //在线处理
    int maxSubArray_online_processing(const vector<int>& nums){
        int len_nums = nums.size();
        int max_sum = MIN;
        int this_sum = 0;
        for( int i = 0; i < len_nums; i++ ){
            this_sum += nums[i];
            max_sum = max(max_sum, this_sum);
            if(this_sum < 0) this_sum = 0;
        }
        return max_sum;
    }
};

3 思考与拓展

3.1 思考

在线处理的时间复杂度为O(n),此外还有一种方法叫做分治,其空间复杂度为O(nlogn),二者的思想都值得细细回味。

3.1.1 其他方法
3.1.1.1 分治法

分治主要有两个步骤,分和治。 把输入的 nums 数组一分为2,递归求左半部分最大子序和 left_max,递归求右半部分的最大子序和right_max,一遍扫描求跨越中间节点的最大子序和 across_mid_max,三者的最大值即为最大子序和。

代码语言:javascript
复制
class Solution {
public:
    const int MIN = -2147483648;
    int maxSubArray(vector<int>& nums) {
        return maxSubArray_divideAndConquer(nums, 0, nums.size() - 1);
    }
    int maxSubArray_divideAndConquer(const vector<int>& nums, const int start, const int end){
        if(start == end) return nums[start];
        int mid = (start + end) / 2;
        //获取左、右部分最大值
        int left_max = maxSubArray_divideAndConquer(nums, start, mid);
        int right_max = maxSubArray_divideAndConquer(nums, mid + 1, end);
        //获取中间最大值
        int left_across_mid_max = MIN;
        int left_across_mid_sum = 0;
        for( int i = mid; i >= start; i-- ){
            left_across_mid_sum += nums[i];
            left_across_mid_max = max(left_across_mid_max, left_across_mid_sum);
        }
        int right_across_mid_max = MIN;
        int right_across_mid_sum = 0;
        for( int i = mid + 1; i <= end; i++ ){
            right_across_mid_sum += nums[i];
            right_across_mid_max = max(right_across_mid_max, right_across_mid_sum);
        }
        int across_mid_max = left_across_mid_max + right_across_mid_max;
        return max(left_max, max(right_max, across_mid_max));
    }
};
3.1.2 复杂度分析

方法

空间复杂度

时间复杂度

在线处理法

O(1)

O(n)

分治法

O(n)

O(nlogn)

3.1.3 难点分析
  1. 在线处理法需要理解如果当前累加的和 this_sum < 0,那么其肯定不会使得后续的子序和更大;
  2. 分治法需要考虑三种可能的最大子列和情况

3.2 拓展

本题可以有很多变形,可以尝试最小子序列和。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-01-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员乔戈里 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 053_(最大子序和)Maximum Subarray
  • 1 问题描述、输入输出与样例
    • 1.1 问题描述
      • 1.2 输入与输出
        • 1.3 样例
          • 1.3.1 样例1
      • 2 思路描述与代码
        • 2.1 思路描述(在线处理法)
          • 2.2 代码
          • 3 思考与拓展
            • 3.1 思考
              • 3.1.1 其他方法
              • 3.1.2 复杂度分析
              • 3.1.3 难点分析
            • 3.2 拓展
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档