LeetCode 30 days Challenge - Day 3

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

Maximum Subarray

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

Example:

1
2
3

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

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.

Solution

题目要求分析：给定一个整型数组，找到其中连续和最大的子数组。

本题是算法导论原题，可以参考原书，以加深理解。

解法一（遍历，追踪最大值）：

维护一个遍历res为最终答案，cur记录当前已经积累的值，当cur < 0时，重置cur为0。

初次接触者可能有两个问题：

为什么cur小于0才重置，而不是cur变小了就重置？

cur变小说明加了一个负数，但“迄今为止”，我们所累加的仍是一个正值。
能保证完备性吗？

能。每次cur的更新意味着一个子数组的结束。不妨考虑：

最坏情况：全是负数的数组，每遍历一个值便更新一次cur，res成功track最大的负数。

最佳情况：全数组非负，直到结束不会更新cur，res成功track整个数组的和和。

其他情况：尽可能地以正数为子数组的第一个元素，遇到负数进行“容忍”，直到该子数组和为负，res成功track所有子数组和中最大的一个。

int maxSubArray(vector<int>& nums) {
    if (nums.empty()) return 0;
    int cur = 0, res = nums[0];
    for (int i : nums) {
        cur += i;
        res = max(cur, res);
        if (cur < 0) cur = 0;
    }
    return res;
}

解法二（分治法）：

这个方法是《算法导论》中介绍的，对每一个数组：

取中点，分成左右两份，数组的最大子数组和可能包括或者不包括中点。
考虑以下情况：
1. 不包括中点，在左边一份：递归地，对左边一份进行求解。
2. 不包括中点，在右边一份：递归地，对左边一份进行求解。
3. 包括中点：中点加上左边一份的最大尾部和以及右边一份的最大头部和。
计算上述三种情况，取最大即为所求。

取题中示例：[-2,1,-3,4,-1,2,1,-5,4]

取中点 -1, 分为：[-2,1,-3,4],-1, [2,1,-5,4]

对[-2,1,-3,4]进行求解
对 [2,1,-5,4]进行求解
包括-1，左边最大尾部和：4+(-3)+1 = 2，右边最大头部和：2+1 = 3

// 包括中点
int crossmid(vector<int>& nums, int l, int mid, int r) { 
    int l_res = INT_MIN, r_res = INT_MIN;

    int cur = 0;
	// 左边最大尾部和
    for (int i = mid; i >=l; i--) {
        cur += nums[i];
        if (cur > l_res) l_res = cur;
    }

    cur = 0;
    // 右边最大头部和
    for (int i = mid+1; i <= r; i++) {
        cur += nums[i];
        if (cur > r_res) r_res = cur;
    }

    return l_res + r_res;
}
// 不包括中点
int side(vector<int>& nums, int l, int r) {
    if (l == r) return nums[l];
    int mid = (l + r) / 2;
    // 求三者最大值
    return max(max(side(nums, l, mid), side(nums, mid + 1, r)),  crossmid(nums, l, mid, r));
}

int maxSubArray(vector<int>& nums) {
    return side(nums, 0, nums.size() - 1);
}

传送门：Maximum Subarray

Karl

Karl's Nest

leetcode-day-3

LeetCode 30 days Challenge - Day 3

Maximum Subarray

Solution