-
Notifications
You must be signed in to change notification settings - Fork 1
/
31_连续子数组的最大和
92 lines (85 loc) · 1.92 KB
/
31_连续子数组的最大和
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <vector>
using namespace std;
/*
题目描述:
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?
*/
class Solution
{
public:
//穷举法,时间复杂度O(N^2)
int FindGreatestSumOfSubArray(vector<int> array)
{
if (array.size() == 0)
{
return 0;
}
int Max = array[0];
int Sum = 0;
for (int i = 0; i < array.size(); ++i)
{
Sum = 0;
int Max1 = Max;
for (int j = i; j < array.size(); ++j)
{
Sum += array[j];
if (Sum > Max)
{
Max1 = Sum;
}
}
if (Max1 > Max)
{
Max = Max1;
}
}
return Max;
}
//贪心法,时间复杂度为O(N)
int FindGreatestSumOfSubArray_Better(vector<int> array)
{
if (array.size() == 0)
{
return 0;
}
int Max = 0xffffffff;
int Sum = 0;
int NegMax = 0x80000000;
for (int i = 0; i < array.size(); ++i)
{
Sum += array[i];
if (Sum < 0)
{
Sum = 0;
}
if (Sum > Max)
{
Max = Sum;
}
if (NegMax < array[i])
{
NegMax = array[i];
}
}
return Max > 0 ? Max : NegMax;
}
};
void Test()
{
//vector<int> ivec = { 6, -3, -2, 7, -15, 1, 2, 2 };
//vector<int> ivec = { 1, -2, 3, 10, -4, 7, 2, -5 };
vector<int> ivec = { -3, -2, -3, -10, -4, -7, -2, -5 };
cout << Solution().FindGreatestSumOfSubArray(ivec) << endl;
}
void Test1()
{
//vector<int> ivec = { 1, -2, 3, 10, -4, 7, 2, -5 };
vector<int> ivec = { -3, -2, -3, -10, -4, -7, -2, -5 };
cout << Solution().FindGreatestSumOfSubArray_Better(ivec) << endl;
}
int main()
{
Test1();
return 0;
}