給定一個(gè)無(wú)序數(shù)組壁肋，求最大的連續(xù)子數(shù)組的和
解法一：
- 思路：暴力解法片任，最大序列肯定以數(shù)組中某個(gè)數(shù)為起點(diǎn)桃犬，則依次遍歷以每個(gè)點(diǎn)為起點(diǎn)的情況
- 時(shí)間復(fù)雜度：O(n平方)
int maxSubSequence1(vector<int> A, int n) {
int max = INT_MIN;
for (int i = 0; i < n; i++) {
int tempSum = 0;
for (int j = i; j < n; j++) {
tempSum += A[j];
max = tempSum > max ? tempSum : max;
}
}
return max;
}
解法二：
-
思路：分治思想颅悉，結(jié)果有三種情況：
- 情況1：最大子序列在左邊部分
- 情況2：最大子序列在右邊部分
- 情況3：最大子序列橫跨左右兩個(gè)部分
然后每次遞歸過(guò)程都返回三者最大即可
時(shí)間復(fù)雜度：O(nlogn)
int maxForThree(int A, int B, int C) {
if (A >= B && A >= C) {
return A;
}
return maxForThree(B, C, A);
}
int maxSubSequence2(vector<int> A, int left, int right) {
if (left == right) {
return A[left];
}
int middle = left + (right - left)/2;
// 左半部分
int leftSum = 0;
int leftMax = INT_MIN;
for (int i = middle; i >= 0; i--) {
leftSum += A[i];
leftMax = leftSum > leftMax ? leftSum : leftMax;
}
// 右半部分
int rightSum = 0;
int rightMax = INT_MIN;
for (int i = middle + 1; i < A.size(); i++) {
rightSum += A[i];
rightMax = rightSum > rightMax ? rightSum : rightMax;
}
return maxForThree(leftMax + rightMax, maxSubSequence2(A, left, middle), maxSubSequence2(A, middle + 1, right));
}
解法三：
- 思路：調(diào)整思考角度嚣镜，暴力解法核心是最大子序列一定是以數(shù)組中某個(gè)數(shù)為起點(diǎn)，轉(zhuǎn)變思維辰狡，最大子序列也一定是以數(shù)組中某個(gè)數(shù)為終點(diǎn)
- 時(shí)間復(fù)雜度：O(n)
int maxSubSequence3(vector<int> A, int n) {
int tempMax = A[0]; // 以該數(shù)結(jié)尾的序列的最大和
int resultMax = A[0];
for (int i = 1; i < n; i++) {
if (tempMax < 0) {
tempMax = A[i];
} else {
tempMax += A[i];
}
resultMax = tempMax > resultMax ? tempMax : resultMax;
}
return resultMax;
}
