Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

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

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 

这道题让求最大子数组之和,并且要用两种方法来解,分别是 O(n) 的解法,还有用分治法 Divide and Conquer Approach,这个解法的时间复杂度是 O(nlgn),那就先来看 O(n) 的解法,这个方法叫做卡达内算法 Kadane's Algorithm,卡卡和齐达内的合体?可以参见维基百科上的这个帖子,定义两个变量 res 和 curSum,其中 res 保存最终要返回的结果,即最大的子数组之和,curSum 初始值为0,每遍历一个数字 num,比较 curSum + num 和 num 中的较大值存入 curSum,然后再把 res 和 curSum 中的较大值存入 res,以此类推直到遍历完整个数组,可得到最大子数组的值存在 res 中,代码如下:

C++ 解法一:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN, curSum = 0;
        for (int num : nums) {
            curSum = max(curSum + num, num);
            res = max(res, curSum);
        }
        return res;
    }
};

Java 解法一:

public class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE, curSum = 0;
        for (int num : nums) {
            curSum = Math.max(curSum + num, num);
            res = Math.max(res, curSum);
        }
        return res;
    }
}

题目还要求我们用分治法 Divide and Conquer Approach 来解,这个分治法的思想就类似于二分搜索法,需要把数组一分为二,分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,求出的最大值分别和左右两边得出的最大值相比较取最大的那一个,代码如下:

C++ 解法二:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) return 0;
        return helper(nums, 0, (int)nums.size() - 1);
    }
    int helper(vector<int>& nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        int lmax = helper(nums, left, mid - 1);
        int rmax = helper(nums, mid + 1, right);
        int mmax = nums[mid], t = mmax;
        for (int i = mid - 1; i >= left; --i) {
            t += nums[i];
            mmax = max(mmax, t);
        }
        t = mmax;
        for (int i = mid + 1; i <= right; ++i) {
            t += nums[i];
            mmax = max(mmax, t);
        }
        return max(mmax, max(lmax, rmax));
    }
};

Java 解法二:

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        return helper(nums, 0, nums.length - 1);
    }
    public int helper(int[] nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        int lmax = helper(nums, left, mid - 1);
        int rmax = helper(nums, mid + 1, right);
        int mmax = nums[mid], t = mmax;
        for (int i = mid - 1; i >= left; --i) {
            t += nums[i];
            mmax = Math.max(mmax, t);
        }
        t = mmax;
        for (int i = mid + 1; i <= right; ++i) {
            t += nums[i];
            mmax = Math.max(mmax, t);
        }
        return Math.max(mmax, Math.max(lmax, rmax));
    }
}

Github 同步地址:

https://github.com/grandyang/leetcode/issues/53

类似题目:

Best Time to Buy and Sell Stock

Maximum Product Subarray 

Degree of an Array

Maximum Absolute Sum of Any Subarray

Maximum Subarray Sum After One Operation

参考资料:

https://leetcode.com/problems/maximum-subarray/

https://leetcode.com/problems/maximum-subarray/discuss/20211/Accepted-O(n)-solution-in-java

https://leetcode.com/problems/maximum-subarray/discuss/20193/DP-solution-and-some-thoughts

https://leetcode.com/problems/maximum-subarray/discuss/20200/Share-my-solutions-both-greedy-and-divide-and-conquer

LeetCode All in One 题目讲解汇总(持续更新中...)

标签智能推荐:

LeetCode高频题目(100)汇总-Java实现

&nbsp;LeetCode高频题目(100)汇总-Java实现&nbsp;&nbsp;&nbsp;【Leetcode-easy-1】TwoSum【Leetcode-easy-2】AddTwoNumbers【Leetcode-easy-3】LongestSubstringWithoutRepeatingCharacters【Leetcode-easy-5】LongestPalindromicSub

C++ 前期准备

在线编译网站:http://www.dooccn.com/cpp/刷题:https://leetcode.com/https://leetcode-cn.com/

Index

Tableofcontents目录TableofcontentsOJ-Improvemyself,better.Leetcode洛谷OJ-Improvemyself,better.Leetcode洛谷

算法-1

1.能少for循环,就少2.与for无关的变量的不进入for循环刷题网址:1.leetcode:https://leetcode.cn/https://leetcode-cn.com/2.牛客网:https://www.nowcoder.com/

8.2

python版按键精灵,pyautogui。未完成,看书deeplearning,刷题leetcode。明日:网络脚本,看书,刷题。

二分搜索常见题

LeetCode:1011.在D天内送达包裹的能力&nbsp;https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/875.爱吃香蕉的珂珂&nbsp;https://leetcode-cn.com/problems/koko-eating-bananas/1482.制作m束花所需的最少天数&nbsp;htt

09-06日记

1.leetcode复习五道2.你不知道的js学习3.webpack学习

总结-二叉树

二叉树:前序遍历:https://leetcode-cn.com/problems/binary-tree-preorder-traversal/中序遍历:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/后序遍历:https://leetcode-cn.com/problems/binary-tree-postorder

11-29日记

1.leetcode两道2.koa源码学习3.跨域知识学习

ArrayList、ArrayDeque与LinkedList区别

https://blog.csdn.net/u011485472/article/details/109124458https://leetcode-cn.com/circle/article/bXc4tx/