C++實(shí)現(xiàn)LeetCode(53.最大子數(shù)組)
[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ù)組之和,并且要用兩種方法來(lái)解,分別是 O(n) 的解法,還有用分治法 Divide and Conquer Approach,這個(gè)解法的時(shí)間復(fù)雜度是 O(nlgn),那就先來(lái)看 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 來(lái)解,這個(gè)分治法的思想就類似于二分搜索法,需要把數(shù)組一分為二,分別找出左邊和右邊的最大子數(shù)組之和,然后還要從中間開(kāi)始向左右分別掃描,求出的最大值分別和左右兩邊得出的最大值相比較取最大的那一個(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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(152.求最大子數(shù)組乘積)
- C++動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)矩陣鏈乘法
- C++動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)查找最長(zhǎng)公共子序列
- C++?動(dòng)態(tài)規(guī)劃算法使用分析
- C++編輯距離(動(dòng)態(tài)規(guī)劃)
- c++動(dòng)態(tài)規(guī)劃經(jīng)典算法
- C++動(dòng)態(tài)規(guī)劃之最長(zhǎng)公子序列實(shí)例
- C++動(dòng)態(tài)規(guī)劃之背包問(wèn)題解決方法
- C++動(dòng)態(tài)規(guī)劃計(jì)算最大子數(shù)組
相關(guān)文章
VC實(shí)現(xiàn)圖片拖拽及動(dòng)畫(huà)的實(shí)例
這篇文章介紹了VC實(shí)現(xiàn)圖片拖拽及動(dòng)畫(huà)的實(shí)例,有需要的朋友可以參考一下2013-08-08
VS2019配置OpenCV時(shí)找不到Microsoft.Cpp.x64.user的解決方法
這篇文章主要介紹了VS2019配置OpenCV時(shí)找不到Microsoft.Cpp.x64.user的解決方法,需要的朋友可以參考下2020-02-02
C++強(qiáng)制轉(zhuǎn)換與智能指針示例詳解
這篇文章主要介紹了C++強(qiáng)制轉(zhuǎn)換與智能指針示例,智能指針(Smart Pointer)是一種抽象的數(shù)據(jù)類型。在程序設(shè)計(jì)中,它通常是經(jīng)由類模板來(lái)實(shí)現(xiàn),借由模板來(lái)達(dá)成泛型,借由類別的析構(gòu)函數(shù)來(lái)達(dá)成自動(dòng)釋放指針?biāo)赶虻拇鎯?chǔ)器或?qū)ο?/div> 2022-11-11
Visual?studio2022?利用glfw+glad配置OpenGL環(huán)境的詳細(xì)過(guò)程
這篇文章主要介紹了Visual?studio2022?利用glfw+glad配置OpenGL環(huán)境,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-10-10
C++容器std::vector的swap()函數(shù)使用方式
這篇文章主要介紹了C++容器std::vector的swap()函數(shù)使用方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
C++ 實(shí)現(xiàn)求最大公約數(shù)和最小公倍數(shù)
這篇文章主要介紹了c++ 實(shí)現(xiàn)求最大公約數(shù)和最小公倍數(shù)的相關(guān)資料,需要的朋友可以參考下2017-05-05
C++靜態(tài)成員變量和靜態(tài)成員函數(shù)的使用方法總結(jié)
下面小編就為大家?guī)?lái)一篇C++靜態(tài)成員變量和靜態(tài)成員函數(shù)的使用方法總結(jié)。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01最新評(píng)論

