给定一个无序数组,求最大的连续子数组的和

解法一:
  • 思路:暴力解法,最大序列肯定以数组中某个数为起点,则依次遍历以每个点为起点的情况
  • 时间复杂度:O(n平方)
1
2
3
4
5
6
7
8
9
10
11
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;
}
解法二:
  • 思路:分治思想,结果有三种情况:

    • 情况1:最大子序列在左边部分
    • 情况2:最大子序列在右边部分
    • 情况3:最大子序列横跨左右两个部分

    然后每次递归过程都返回三者最大即可

  • 时间复杂度:O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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));
}
解法三:
  • 思路:调整思考角度,暴力解法核心是最大子序列一定是以数组中某个数为起点,转变思维,最大子序列也一定是以数组中某个数为终点
  • 时间复杂度:O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxSubSequence3(vector<int> A, int n) {
int tempMax = A[0]; // 以该数结尾的序列的最大和
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;
}