快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(53.最大子數(shù)組)

更新時(shí)間：2021年07月16日 08:37:42 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(53.最大子數(shù)組),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 53. Maximum Subarray 最大子數(shù)組

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

Example:

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.

這道題讓求最大子數(shù)組之和，并且要用兩種方法來解，分別是 O(n) 的解法，還有用分治法 Divide and Conquer Approach，這個(gè)解法的時(shí)間復(fù)雜度是 O(nlgn)，那就先來看 O(n) 的解法，定義兩個(gè)變量 res 和 curSum，其中 res 保存最終要返回的結(jié)果，即最大的子數(shù)組之和，curSum 初始值為0，每遍歷一個(gè)數(shù)字 num，比較 curSum + num 和 num 中的較大值存入 curSum，然后再把 res 和 curSum 中的較大值存入 res，以此類推直到遍歷完整個(gè)數(shù)組，可得到最大子數(shù)組的值存在 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 來解，這個(gè)分治法的思想就類似于二分搜索法，需要把數(shù)組一分為二，分別找出左邊和右邊的最大子數(shù)組之和，然后還要從中間開始向左右分別掃描，求出的最大值分別和左右兩邊得出的最大值相比較取最大的那一個(gè)，代碼如下：

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));
    }
}

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(53.最大子數(shù)組)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)最大子數(shù)組內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: