求一个向量的任何连续子向量的最大和
比如向量(31,-41,59,26,-53,58,97,-93,-23,84);
最大和是从59到97即为187
|
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
#include<stdio.h>
#include<stdlib.h>
//两者的最大值
int max( int x, int y );
//三者的最大值
int max2( int x, int y, int z );
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len );
//原始基础上变体版,复杂度为T(n)=O(n*n)
int oringinal_ex( int v[], int len );
//分治法,复杂度为T(n)=O(n*log(n))
/*
*分治法的思想是：将原数组分成两部分，要求的最大值
*要么在左边这部分里面，要么在右边这部分里面
*要么就在左右相交的交界处
*/
int divAndCon( int v[], int low, int high );
//扫描法,复杂度为T(n)=O(n)
int scan(int v[], int len);
void main()
{
int i = 0;
int v[] = {31,-41,59,26,-53,58,97,-93,-23,84};
int len = 0;
int result;
len = sizeof(v) / sizeof(int);
printf("oringinal datas:\n");
for( i = 0; i < len; i++ )
{
printf("%d\t",v[i]);
}
printf("\n");
//最原始的算法
result = oringinal(v,len);
printf("oringinal(v,len):%d\n",result);
//最原始变体的算法
result = oringinal_ex(v,len);
printf("oringinal_ex(v,len):%d\n",result);
//分治法
result = divAndCon(v,0,len-1);
printf("divAndCon(v,0,len):%d\n",result);
//扫描法
result = scan(v,len);
printf("scan(v,len):%d\n",result);
}
//两者的最大值
int max( int x, int y )
{
if( x < y )
{
x = y;
}
return x;
}
//三者的最大值
int max2( int x, int y, int z )
{
if( x < y )
{
x = y;
}
if( x < z )
{
x = z;
}
return x;
}
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len )
{
int maxsofar = 0;
int i;
int j;
int sum = 0;
//通过双层循环逐步扫描，通过max( sum, maxsofar)获得当前最大值
for( i = 0; i < len; i++ )
{
sum = 0;
for( j = i; j < len; j++ )
{
sum += v[j];
maxsofar = max( sum, maxsofar );
}
}
return maxsofar;
}
//原始基础上变体版,复杂度为T(n)=O(n*n)
int oringinal_ex( int v[], int len )
{
int i = 0;
int j = 0;
int sum = 0;
int maxsofar = 0;
int *cumarr = ( int * )malloc( len * sizeof(int) );
for( i = 0; i < len; i++ )
{
if( i == 0 )
{
cumarr[0] = v[i];
}
else
{
cumarr[i] = cumarr[i-1] + v[i];
}
}
for( i = 0; i < len; i++ )
for( j = i; j < len; j++ )
{
if( i == 0 )
{
sum = cumarr[i];
}
else
{
sum = cumarr[j] - cumarr[i-1];
}
maxsofar = max(maxsofar,sum);
}
return maxsofar;
}
//分治法,复杂度为T(n)=O(n*log(n))
int divAndCon( int v[], int low, int high )
{
int mid = 0;
int lmax = 0;
int rmax = 0;
int sum = 0;
int i = 0;
if( low > high )
{
return 0;
}
if( low == high )
{
return max(0,v[low]);
}
mid = ( low + high ) / 2;
lmax = sum = 0;
for( i = mid; i >= low; i-- )
{
sum += v[i];
lmax = max(lmax,sum);
}
rmax = sum = 0;
for( i = mid + 1; i <= high; i++ )
{
sum +=v[i];
rmax = max(rmax,sum);
}
return max2(lmax + rmax,divAndCon(v,low,mid),divAndCon(v,mid+1,high));
}
//扫描法,复杂度为T(n)=O(n)
int scan(int v[], int len)
{
int maxsofar = 0;
int maxendinghere = 0;
int i = 0;
for( i =0; i < len; i++ )
{
maxendinghere = max(maxendinghere + v[i],0);
maxsofar = max(maxsofar,maxendinghere);
}
return maxsofar;
}
|
求一个向量的任何连续最接近0的子向量的和
比如向量(31,-41,59,26,-53,58,97,-93,-23,84);
最大和是从97到-93即为4
|
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
|
#include<stdio.h>
#include<math.h>
//返回最接近0的数
int closeZero( int x, int y );
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len );
void main()
{
int i = 0;
int v[] = {31,-41,59,26,-53,58,97,-93,-23,84};
int len = 0;
int result;
len = sizeof(v) / sizeof(int);
printf("oringinal datas:\n");
for( i = 0; i < len; i++ )
{
printf("%d\t",v[i]);
}
printf("\n");
//最原始的算法
result = oringinal(v,len);
printf("oringinal(v,len):%d\n",result);
}
//返回最接近0的数
int closeZero( int x, int y )
{
if( abs(x) > abs(y) )
{
x = y;
}
return x;
}
//最原始的算法，复杂度为T(n)=O(n*n)
int oringinal( int v[], int len )
{
int sofar = v[0];
int i;
int j;
int sum = 0;
for( i = 0; i < len; i++ )
{
sum = 0;
for( j = i; j < len; j++ )
{
sum += v[j];
sofar = closeZero( sum, sofar );
}
}
return sofar;
}
|
运行结果：
