webcenterol

浏览: 911410 次

最近访客更多访客>>

athena507

wyx065747

一往无前bhz

u012363178

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1745)

社区版块

存档分类

2012-02 ( 2)
2011-11 ( 10)
2011-10 ( 112)
更多存档...

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记用C++/lua/python/bash的四重实现（3）最大子序列和问题

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记用C++/lua/python/bash的四重实现（3）最大子序列和问题

write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss著人民邮电大学出版中文版第39-43面，图2-5，2-6,2-7,2-8最大子序列和问题的解

总算有点技术含量了，呵呵，虽然说重复实现一下代码不难（不就是相当于翻译嘛），但是算法4为什么是正确的需要好好理解一下。

以下为实现部分:

CPP:

1 //
2 // Maximum contiguous subsequence sum algorithm 1 - 4, worst to best
3 // From <<Data Structures and Algorithm Analysis in C++>> by Mark Allen Weiss
4 //
5 //
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <vector>
9 usingnamespacestd;
10
11
12
13 intmaxSubSum1( constvector<int> &a)
14 {
15 intmaxSum = 0;
16
17 for(inti=0; i<(int)a.size(); ++i)
18 for(intj=i; j<(int)a.size(); ++j)
19 {
20 intthisSum = 0;
21
22 for(intk=i; k<=j; ++k)
23 thisSum += a[k];
24
25 if(thisSum > maxSum)
26 maxSum = thisSum;
27 }
28 returnmaxSum;
29 }
30
31 intmaxSubSum2( constvector<int> &a)
32 {
33 intmaxSum = 0;
34
35 for(inti=0; i<(int)a.size(); ++i)
36 {
37 intthisSum = 0;
38 for(intj=i; j<(int)a.size(); ++j)
39 {
40 thisSum += a[j];
41
42 if( thisSum > maxSum)
43 maxSum = thisSum;
44 }
45 }
46 returnmaxSum;
47 }
48
49 intmax3(inta, intb, intc)
50 {
51 return((a < b)?((b < c)?c:b):((a < c)?c:a));
52 }
53
54
55 intmaxSumRec( constvector<int> &a, intleft, intright)
56 {
57 if(left == right)
58 if( a[left] > 0)
59 returna[left];
60 else
61 return0;
62
63 intcenter = (left + right) / 2;
64 intmaxLeftSum = maxSumRec(a, left, center);
65 intmaxRightSum = maxSumRec(a, center + 1, right);
66
67 intmaxLeftBorderSum = 0;
68 intleftBorderSum = 0;
69
70 for(inti=center; i >=left; --i)
71 {
72 leftBorderSum += a[i];
73 if(leftBorderSum > maxLeftBorderSum)
74 maxLeftBorderSum = leftBorderSum;
75 }
76
77 intmaxRightBorderSum = 0,rightBorderSum = 0;
78 for(intj = center + 1; j <= right; ++j)
79 {
80 rightBorderSum += a[j];
81 if(rightBorderSum > maxRightBorderSum)
82 maxRightBorderSum = rightBorderSum;
83 }
84
85
86 returnmax3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
87 }
88
89 intmaxSubSum3(constvector<int> &a)
90 {
91 returnmaxSumRec(a, 0, a.size() - 1);
92 }
93
94 intmaxSubSum4( constvector<int> &a)
95 {
96 intmaxSum = 0, thisSum = 0;
97
98 for( intj = 0; j< (int)a.size(); ++j)
99 {
100 thisSum += a[j];
101
102 if(thisSum > maxSum)
103 maxSum = thisSum;
104 elseif(thisSum < 0)
105 thisSum = 0;
106 }
107
108 returnmaxSum;
109 }
110
111
112
113 intmain(intargc, char* argv[])
114 {
115 // for easy
116 inta[] = { -2, 11, -4, 13, -5, -2};
117 vector<int> lvec(a, a + sizeof(a)/sizeof(int));
118
119 printf("maxSubSum1(lvec)):%d/n",maxSubSum1(lvec));
120 printf("maxSubSum2(lvec)):%d/n",maxSubSum2(lvec));
121 printf("maxSubSum3(lvec)):%d/n",maxSubSum3(lvec));
122 printf("maxSubSum4(lvec)):%d/n",maxSubSum4(lvec));
123
124
125 exit(0);
126 }
127

LUA:

1 #!/usr/bin/env lua
2
3
4 functionmaxSubSum1(a)
5 assert(type(a) == "table", "Argument a must be a number array.")
6
7 localmaxSum = 0
8
9 fori=1,#a do
10 forj=i,#ado
11 localthisSum = 0
12 fork=i,j do
13 thisSum = thisSum + a[k]
14 end
15
16 ifthisSum > maxSum then
17 maxSum = thisSum
18 end
19 end
20 end
21
22 returnmaxSum
23 end
24
25 functionmaxSubSum2(a)
26 assert(type(a) == "table", "Argument a must be a number array.")
27
28 localmaxSum = 0
29
30 fori=1,#a do
31 localthisSum = 0
32
33 forj=i,#a do
34 thisSum = thisSum + a[j]
35
36 if(thisSum > maxSum) then
37 maxSum = thisSum
38 end
39 end
40 end
41 returnmaxSum
42 end
43
44 functionmax3(n1, n2, n3)
45 return(n1 > n2 and((n1 > n3) andn1 orn3) or((n2 > n3) andn2 orn3))
46 end
47
48 -- require math
49
50 functionmaxSumRec(a, left, right)
51 assert(type(a) == "table", "Argument a must be a number array.")
52 assert(type(left) == "number"andtype(right) == "number",
53 "Argument left&rightmust be number arrays.")
54
55 ifleft == right then
56 ifa[left] > 0then
57 returna[left]
58 else
59 return0
60 end
61 end
62
63 localcenter = math.floor((left + right) / 2)
64 localmaxLeftSum = maxSumRec(a, left, center)
65 localmaxRightSum = maxSumRec(a, center+1, right)
66
67 localmaxLeftBorderSum = 0
68 localleftBorderSum = 0
69 fori=center,left,-1do
70 leftBorderSum = leftBorderSum + a[i]
71 ifleftBorderSum > maxLeftBorderSum then
72 maxLeftBorderSum = leftBorderSum
73 end
74 i = i - 1
75 end
76
77 localmaxRightBorderSum = 0
78 localrightBorderSum = 0
79 forj=center+1,right do
80 rightBorderSum = rightBorderSum + a[j]
81 ifrightBorderSum > maxRightBorderSum then
82 maxRightBorderSum = rightBorderSum
83 end
84 end
85
86 returnmax3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum)
87 end
88
89 functionmaxSubSum3(a)
90 assert(type(a) == "table", "Argument a must be a number array.")
91
92 returnmaxSumRec(a, 1, 6)
93
94 end
95
96 functionmaxSubSum4(a)
97 assert(type(a) == "table", "Argument a must be a number array.")
98
99 localmaxSum = 0
100 localthisSum = 0
101
102 fori=1,#a do
103 thisSum = thisSum + a[i]
104
105 ifthisSum > maxSum then
106 maxSum = thisSum
107 elseifthisSum < 0then
108 thisSum = 0
109 end
110
111 end
112
113 returnmaxSum
114
115 end
116
117 -- Test Code
118
119 t = {-2, 11, -4, 13, -5, -2}
120
121 print("maxSubSum1(t):".. maxSubSum1(t))
122 print("maxSubSum2(t):".. maxSubSum2(t))
123 print("maxSubSum3(t):".. maxSubSum3(t))
124 print("maxSubSum4(t):".. maxSubSum4(t))
125
126
127

PYTHON:

1 #!/usr/bin/env python
2
3 # How Short and Clean it is I shocked as a CPP Programmer
4 defmaxSubSum1(a):
5 maxSum = 0
6
7 fori ina:
8 forj ina[i:]:
9 thisSum = 0
10
11 fork ina[i:j]:
12 thisSum += k
13
14 ifthisSum > maxSum:
15 maxSum = thisSum
16
17 returnmaxSum
18
19 defmaxSubSum2(a):
20 maxSum = 0
21
22 fori ina:
23 thisSum = 0
24 forj ina[i:]:
25 thisSum += j
26
27 ifthisSum > maxSum:
28 maxSum = thisSum
29
30 returnmaxSum
31
32
33 defmax3(n1, n2, n3):
34 return((n1 ifn1 > n3 elsen3) ifn1 > n2 else(n2 ifn2 > n3 elsen3))
35
36 defmaxSumRec(a, left, right):
37 ifleft == right:
38 ifa[left] > 0:
39 returna[left]
40 else:
41 return0
42
43 center = (left + right)//2
44 maxLeftSum = maxSumRec(a, left, center)
45 maxRightSum = maxSumRec(a, center+1, right)
46
47 maxLeftBorderSum = 0
48 leftBorderSum = 0
49 fori ina[center:left:-1]:
50 leftBorderSum += i
51 ifleftBorderSum > maxLeftBorderSum:
52 maxLeftBorderSum = leftBorderSum
53
54 maxRightBorderSum = 0
55 rightBorderSum = 0
56 fori ina[center+1:right]:
57 rightBorderSum += i
58 ifrightBorderSum > maxRightBorderSum:
59 maxRightBorderSum = rightBorderSum
60
61 returnmax3(maxLeftSum, maxRightBorderSum, maxLeftBorderSum + maxRightBorderSum)
62
63 defmaxSubSum3(a):
64 returnmaxSumRec(a, 0, len(a)-1)
65
66 defmaxSubSum4(a):
67 maxSum = 0
68 thisSum = 0
69
70 fori ina:
71 thisSum += i
72
73 ifthisSum > maxSum:
74 maxSum = thisSum
75 elifthisSum < 0:
76 thisSum = 0
77
78 returnmaxSum
79
80 deftest():
81 t = (-2, 11, -4, 13, -5, -2)
82
83 print"maxSubSum1:%d"% maxSubSum1(t)
84 print"maxSubSum2:%d"% maxSubSum2(t)
85 print"maxSubSum3:%d"% maxSubSum3(t)
86 print"maxSubSum4:%d"% maxSubSum4(t)
87
88 if__name__ == '__main__':
89 test()

BASH:

1 #!/usr/bin/env bash
2 绕了我吧。。。。。特别是算法二。。复杂的递归用bash来写就是自虐。Bash似乎本来就不是用来描述算法用的，呵呵，以后没有什么事一般就不把bash搬出来了。

write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie

分享到：

一个无聊男人的疯狂《数据结构与算法分析-C ... | Windows中多指针输入技术的实现与应用(10 ...

2008-11-23 03:33
浏览 559
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记用C++/lua/python/bash的四重实现（3）最大子序列和问题

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记用C++/lua/python/bash的四重实现（3）最大子序列和问题

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现（3） 最大子序列和问题

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现（3） 最大子序列和问题

评论

发表评论

相关推荐

最近访客更多访客>>

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记用C++/lua/python/bash的四重实现（3）最大子序列和问题

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记用C++/lua/python/bash的四重实现（3）最大子序列和问题