标题:[讨论]max-subsequence problem!-->aipb2007转移
只看楼主
aipb2007
Rank: 8Rank: 8
来 自:CQU
等 级:贵宾
威 望:40
帖 子:2879
专家分:7
注 册:2007-3-18
 问题点数:0 回复次数:5 
[讨论]max-subsequence problem!-->aipb2007转移
在别的论坛看到的,给定一个整形数组,设计代码找出数组中连续位置之和最大的跨度。
跨度个数不限,比如全都是正数,那肯定是整个数组了。
有正有负的话就要考虑哪一段和最大。把索引位置找到。

详细描述看2楼!

不知道我说清楚没有!
我想了下可以用循环解决。但是肯定还有更好的方法,大家一起想想,把自己的贴出来!

[此贴子已经被作者于2007-6-11 10:10:25编辑过]

搜索更多相关主题的帖子: problem 整形 跨度 正数 
2007-06-09 22:43
HJin
Rank: 6Rank: 6
等 级:贵宾
威 望:27
帖 子:401
专家分:0
注 册:2007-6-9
得分:0 

/*---------------------------------------------------------------------------
File name: max_subseq2.cpp
Author: HJin


The problem is called the max-subsequence problem. This implementation
compiles and runs under VS2005.


Sample ouput:

3 73 -95 42 43 29 -30 -87 74 -53 22 74 -91 -1 -27 -8 -14 26 -67 -74
max subsequence starts at index 8
max subsequence ends at index 11
74-53+22+74 = 117
117


Reference:

Mark Allen Weiss: Data Structures and Algorithm Analysis in C


HJin's apology:

Working on a system which has no Chinese input. What a pain!
*/


#include <iostream>
#define DIM(x) sizeof((x)) /sizeof ((x)[0])

using namespace std;

/**
max_subseq() does not work for an array of all negative numbers.
I will leave it for you to refine it.
*/
int max_subseq(int *a, int n);

/**
Print the soln to the max-subseq problem.
*/
void printSoln(int *a, int best_i, int best_j, int maxSum);


/**
Print an array of size n.
*/
void print(int *a, int n);


int main(int argc, char** argv)
{
int a[] = {3, 73, -95, 42, 43, 29, -30, -87, 74, -53, 22, 74, -91, -1, -27, -8, -14, 26, -67, -74};

print(a, DIM(a));
cout<<max_subseq(a, DIM(a))<<endl;


return 0;
}


void printSoln(int *a, int best_i, int best_j, int maxSum)
{
int k;

// print out messages
cout<<"max subsequence starts at index "<<best_i<<endl;
cout<<"max subsequence ends at index "<<best_j<<endl;
cout<<a[best_i];

for(k=best_i+1; k<=best_j; ++k)
if(a[k] >=0 )
cout<<"+"<<a[k];
else
cout<<a[k];

cout<<" = "<<maxSum<<endl;
}

/** The algorithm uses O(1) space and runs in O(n) time and it is online.
The following is Mark Allen Weiss's comment:


An extra advantage of this algorithm is that it makes only one pass through
the data, and once a[i] is read and processed, it does not need to be
remembered. Thus, if the array is on a disk or tape, it can be read
sequentially, and there is no need to store any part of it in main memory.
Furthermore, at any point in time, the algorithm can correctly give an
answer to the subsequence problem for the data it has already read (the
other algorithms do not share this property). Algorithms that can do
this are called on-line algorithms. An on-line algorithm that requires
only constant space and runs in linear time is just about as good
as possible.

maxSum --- stores the max sum of the max-subseq
best_i --- stores the starting index of the max-subseq
best_j --- stores the ending index of the max-subseq
*/
int max_subseq(int *a, int n)
{
int maxSum = 0;
int thisSum = 0;
int bestStart = -1;
int bestEnd = -1;
int i = 0;
int j;

/**
to make it work for all kinds of input, do some extra work
before this loop.
*/
for (j = 0; j<n; ++j)
{
thisSum += a[j];

if ( thisSum > maxSum )
{
maxSum = thisSum;
bestStart = i;
bestEnd =j;
}

if ( thisSum < 0 )
{
thisSum = 0;
i = j+1;
}

}

// print the soln
printSoln(a, bestStart, bestEnd, maxSum);

return maxSum;
}

void print(int *a, int n)
{
for(int i=0; i<n; ++i)
cout<<a[i]<<" ";
cout<<endl;
}

[此贴子已经被作者于2007-6-9 23:59:35编辑过]


I am working on a system which has no Chinese input. Please don\'t blame me for typing English.
2007-06-09 23:55
aipb2007
Rank: 8Rank: 8
来 自:CQU
等 级:贵宾
威 望:40
帖 子:2879
专家分:7
注 册:2007-3-18
得分:0 
Good algorithm.
Very detailed.
Thanks,any method else?

Fight  to win  or  die...
2007-06-10 14:08
HJin
Rank: 6Rank: 6
等 级:贵宾
威 望:27
帖 子:401
专家分:0
注 册:2007-6-9
得分:0 
回复:(aipb2007)Good algorithm.Very detailed.Tha...
I am very sorry again that I have to type English.

Yes, there are a few other algorihtms for sovling this classical max-subsequence problem. But all of them runs in Omega(n x lg n) time at least. I would suggest you read Weiss's book --- freely available from bt.

Meanwhile, you want to modify your post's title (and move it to the algorithm board) so that every visitor of this site may benefit from our discussion.

God bless China.


I am working on a system which has no Chinese input. Please don\'t blame me for typing English.
2007-06-11 09:43
aipb2007
Rank: 8Rank: 8
来 自:CQU
等 级:贵宾
威 望:40
帖 子:2879
专家分:7
注 册:2007-3-18
得分:0 
回复:(HJin)回复:(aipb2007)Good algorithm.Ver...
Thanks for your suggestion,I am a learner of data structure & algorithm.What's whole name the book you refer to?
Are you in abroad?
hehe~

Fight  to win  or  die...
2007-06-11 10:01
roy_guo
Rank: 1
等 级:新手上路
帖 子:107
专家分:0
注 册:2006-4-27
得分:0 
Thanks, very professional!

彪悍的人生不需要解释~~~
2007-06-13 23:48



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-146245-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 1.034054 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved