专栏首页Leetcode名企之路【Leetcode】53. 最大子序和

【Leetcode】53. 最大子序和

题目

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

题解

动规的经典题目。遍历数组,累加,当累加的值小于0时,从下一元素开始再从新累加。在这个过程中记录下最大的累加值就可以了。

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int current = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (current < 0) {
                current = nums[i];
            } else {
                current += nums[i];
            }
            res = Math.max(current, res);
        }
        return res;
    }
}

这个题目还让用分而治之的方法,那怎么分治呢?具有最大和的子序列存在于一下三种情况之中:

  1. 该最大和子序列存在于其上一级子序列的左半部分中
  2. 该最大和子序列存在于其上一级子序列的右半部分中
  3. 该最大和子序列存在于其上一级子序列的中间部分(既从中间点向左右延伸的序列)

情况1和情况2可以通过迭代(recursion)解决。

情况3可以通过由中间节点开始,向左计算左半部分的和的最大值,向右计算右半部分的和的最大值,然后叠加得到。这种方法需要O(n)时间。

该段代码运行时间符合T(n) = 2*T(n/2) + O(n)。

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

    public int maxSubArray(int[] nums, int left, int right) {
        if (left > right) {
            return Integer.MIN_VALUE;
        } else if (left == right) {
            return nums[left];
        } else {
            int middle = (right - left) / 2 + left;
            int leftMax = maxSubArray(nums, left, middle);
            int rightMax = maxSubArray(nums, middle + 1, right);
            int sum = 0;
            int maxToLeft = Integer.MIN_VALUE;
            for (int i = middle; i >= left; i--) {
                sum += nums[i];
                maxToLeft = Math.max(maxToLeft, sum);
            }
            sum = 0;
            int maxToRight = Integer.MIN_VALUE;
            for (int i = middle + 1; i <= right; i++) {
                sum += nums[i];
                maxToRight = Math.max(maxToRight, sum);
            }
            int result = maxToLeft + maxToRight;
            result = Math.max(result, leftMax);
            result = Math.max(result, rightMax);
            return result;
        }
    }
}

每日英文

  • uneconomic (adj) 不经济的
  • economics (n) 经济
  • socioeconomic (adj) 社会经济的
  • economically (adv) 节俭地
  • financial (a.) 金融的
  • financial crisis 金融危机
  • fiscal (a) 财政的

本文分享自微信公众号 - Leetcode名企之路(DailyLeetCode),作者:码蹄疾

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Leetcode】108. 将有序数组转换为二叉搜索树

    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    Leetcode名企之路
  • 【Leetcode】55. 跳跃游戏

    给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1:

    Leetcode名企之路
  • 【Leetcode】137.只出现一次的数字 II

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

    Leetcode名企之路
  • LeetCode 209. Minimum Size Subarray Sum(DP)

    题解:可以用动态规划,我就是用动态规划过的,但是确实不是最简单的解法,看了题解最简单的是双指针,

    ShenduCC
  • Single Number III

    Tyan
  • 【LeetCode】494. 目标和

    给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一...

    韩旭051
  • leetcode哈希表之两数之和

    这里利用HashMap来存储目标值与当前值的差值及其索引,遍历nums数组,遇到存在的key则直接返回。

    codecraft
  • leetcode哈希表之两数之和

    这里利用HashMap来存储目标值与当前值的差值及其索引,遍历nums数组,遇到存在的key则直接返回。

    codecraft
  • 【LeetCode】198. 打家劫舍 递归递推

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小...

    韩旭051
  • Two Sum

    Given an array of integers, return indices of the two numbers such that they add...

    Tyan

扫码关注云+社区

领取腾讯云代金券