1. 題目
1.1 英文題目
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
1.2 中文題目
給定一個整數陣列 nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，
1.3輸入輸出
| 輸入 | 輸出 |
|---|---|
| nums = [-2,1,-3,4,-1,2,1,-5,4] | 6 |
| nums = [1] | 1 |
| nums = [5,4,-1,7,8] | 23 |
1.4 約束條件
- 1 <= nums.length <= 3 * 104
- -105 <= nums[i] <= 105
2. 實驗平臺
IDE：VS2019
IDE版本：16.10.1
語言：c++11
3. 程式
3.1 測驗程式
#include "Solution.h"
#include <vector> // std::vector
#include<iostream> // std::cout
using namespace std;
// 主程式
void main()
{
// 輸入
vector<int> nums = { -100000 };
Solution solution; // 實體化Solution
int k = solution.maxSubArray(nums); // 主功能
// 輸出
cout << k << endl;
}
3.2 功能程式
3.2.1 窮舉遍歷法
（1）代碼
#pragma once
#include<vector> // std::vector
using namespace std;
//主功能
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 暴力求解
int maxValue = https://www.cnblogs.com/yunmeng-shi/archive/2021/06/27/-100000;
for (int i = 0; i < nums.size(); i++) //遍歷起始值
{
int nowSub = 0;
for (int j = i; j < nums.size(); j++) // 全部遍歷一遍
{
nowSub += nums[j];
if (nowSub > maxValue) maxValue = nowSub;
}
}
return maxValue;
}
};
（2）解讀
該方法是最容易想到的方法，暴力求解，運用滑動視窗法進行遍歷，分別得到以某個為開頭的序列進行求最大值，并隨遍歷的進行實時更新該最大值，復雜度為O(\(n^2\))，
3.2.2 動態規劃法
（1）代碼
#pragma once
#include<vector> // std::vector
using namespace std;
//主功能
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 動態規劃（時間復雜度O(n)，空間復雜度O(n))
int length = nums.size();
vector<int> dp(length); // 存盤每次遞回的最大值
dp[0] = nums[0];
for (int i = 1; i < length; i++)
dp[i] = max(dp[i - 1] + nums[i], nums[i], [](int a, int b) {return a > b ? a : b; }); // Lamda運算式
//求dp中的最大值
int maxSub = -100000;
for (auto j : dp) // c++11中基于范圍的for回圈（Range-based for loop）
if (maxSub < j)
dp[j] = maxSub;
return maxSub;
}
};
（2）思路
參考：https://zhuanlan.zhihu.com/p/85188269
3.2.3 kadane演算法
（1）代碼
#pragma once
#include<vector> // std::vector
using namespace std;
//主功能
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// kadane演算法（時間復雜度O(n)，空間復雜度O(1))
int length = nums.size();
int maxSub = nums[0]; // 慢指標
int maxSubTemp = nums[0]; //快指標
for (auto i : nums)
{
maxSubTemp = max(maxSubTemp + nums[i], nums[i], [](int a, int b) {return a > b ? a : b; }); // Lamda運算式
if (maxSubTemp > maxSub) // 若當前最大值大于總最大值，則總最大值更新
maxSub = maxSubTemp;
}
return maxSub;
}
};
（2）解讀
kadane演算法是在動態規劃法的基礎上加上快慢指標法，快指標指向以i為結尾的子陣列最大值之和，慢指標指向迄今為止的子陣列最大值之和
3.3.4 分治法（divide and conquer）
（1）代碼
pragma once
include // std::vector
//#include<limits.h> // INT_MIN整型最小值
include // std::max
using namespace std;
//主功能
class Solution {
public:
int maxSubArray(vector
if (nums.empty()) return 0;
return helper(nums, 0, (int)nums.size() - 1);
}
int helper(vector
{
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));
}
};
參考：https://www.cnblogs.com/grandyang/p/4377150.html
（2）解讀
參考：https://www.jianshu.com/p/3a38d523503b
4. 相關知識
（1）滑動視窗法
滑動視窗其實就是選取部分序列作為視窗，視窗不停移動，直至找到答案，感覺這更像一種思想，
詳細介紹可以參考：https://www.cnblogs.com/huansky/p/13488234.html
(2) Lamda運算式
Lamda運算式可以直接在需要呼叫函式的位置定義短小精悍的函式，而不需要預先定義好函式,但是不便于復用，適用于比較簡單且不需要復用的函式，寫法為：
func(input1,input2,[],(type1 parameter1，type2 parameter2){函式;}）
詳細介紹參考：https://blog.csdn.net/A1138474382/article/details/111149792
(3) 基于范圍的for回圈（Range-based for loop）
c++11中加入的新特性，類似于python,matlab等面向物件語言的for回圈，寫法為：
for(auto i:array){;}
詳細介紹參考：https://blog.csdn.net/hailong0715/article/details/54172848
（4）kadane演算法
參考：https://zhuanlan.zhihu.com/p/85188269
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288559.html
標籤：其他
上一篇：糟糕程式員的編程風格。。。