|
|
求一个数组中最大的相邻元素之和
举例：
数组m如下：2 3 -6 3 4 3 -2 5 2 -3
则结果为m[3-8]之和15
| yuxh 回复于：2004-12-28 20:27:41
| 这个题还是有一定难度的
[code:1:d75ca1f6ff]void MaxSum(int *m, int n)
{
int i, start=0, end=0, max, sum, start1=0, end1=0, sum1=0;
sum = max= m[0];
if(m[0] > 0) sum1 = m[0];
for(i=1; i<n; i++) {
if(m[i] > 0 && sum1 == 0)
start1 = i;
sum1 += m[i];
if(sum1 > 0) end1 = i;
else sum1 = 0;
if(sum1 > 0 && sum1 > max) {
start = start1;
end = end1;
max = sum1;
}
sum += m[i];
if(sum > max) {
if(end < i-1 ) {
start = end+2;
max = sum - max - m[end+1];
sum = max;
}
else
max = sum;
end = i;
}
}
printf("start %d, end %d, sum %d\n", start, end, max);
}
main()
{
int m[10] = {2,3,-6,3,4,3,-2,5,2,-3};
MaxSum(m, 10);
}
[/code:1:d75ca1f6ff]
自己感觉差不多
| | aero 回复于：2004-12-28 22:40:52
| 题是啥意思啊？没明白。
| | yuxh 回复于：2004-12-29 08:42:05
| 就是把相邻的数加起来，取最大值
2 3 -6 3 4 3 -2 5 2 -3 中
3+4+3+(-2)+5+2=15是相邻数相加最大的
下标是从3到8号
| | liulang0808 回复于：2004-12-29 10:51:36
| 用循环嵌套可以的!不过好象比较浪费资源的!
| | wangxg2 回复于：2004-12-29 11:10:04
| 不对啊！如果全是负数，比如-2，-3，-1，.....，结果应该是-1，而上面的结果出来只是-2。
| | liulang0808 回复于：2004-12-29 11:12:04
| C的语法已经不太熟悉了,简单描述如下:
MAX=M[0]是最终的最大值;
K为中间作为比较用的;
FOR (I=0;I<=N;I++) 其中N是数组的的大小
{K=M[I];
FOR (J=I;J<=N-1;I++)
{IF (MAX<K) THEN MAX=K;
K=K+M[J+1];
}
}
已经两年多没有搞编程方面的东西了.
可能存在错误,请指教!
| | yuxh 回复于：2004-12-29 11:13:09
| 考虑下面的这一种普遍情况：
.......m[start]....m[end].....m[start1].....m[end1] m[i]
其中从start到end是结点i之前(称之为“目前”)相邻和最大的序列，和为max
从start1到end1(end1=i-1)是目前相加和>0的最长序列，和为sum1，如果这样的序列不存在，则sum1=0
用sum表示从start到目前的和
现在新加入了一个结点m[i]，看看最大相邻和序列会发生什么样的变化：
1、sum1 += m[i]; 若sum1 > max，则从start1到i就变成了最大序列，修正start，end，max；
sum1 < 0，则表示最近的相邻和>0的序列不存在了，sum1 = 0;
否则，修正end1, sum1
2、经过上一步调整后，sum+=m[i]; 如果sum > max，则从start到i就最成了最大序列，修正end，max
其它的情况保持不变
只需对序列扫描一遍，即可得到相邻和最大序列，O(n)
| | aero 回复于：2004-12-29 11:14:35
| ^_^，全是负数，应该是0吧。因为什么也不加。
| | yuxh 回复于：2004-12-29 11:26:24
| [quote:f74f43b509="wangxg2"]不对啊！如果全是负数，比如-2，-3，-1，.....，结果应该是-1，而上面的结果出来只是-2。[/quote:f74f43b509]
:em06: 是有这么个问题
所以sum1不应该是最近>0的最长序列，而应该是最近最大或和>0的最长序列
改一下：
[code:1:f74f43b509]void MaxSum(int *m, int n)
{
int i, start=0, end=0, max, sum, start1=0, end1=0, sum1=0;
sum = max= m[0];
sum1 = m[0];
for(i=1; i<n; i++) {
if(m[i] > sum1 && sum1 <= 0) {
start1 = end1 = i;
sum1 = m[i];
}
else {
sum1 += m[i];
if(sum1 > 0) end1 = i;else sum1=m[i];
}
if(sum1 > max) {
start = start1;
end = end1;
max = sum1;
}
sum += m[i];
if(sum > max) {
if(end < i-1 ) {
start = end+2;
max = sum - max - m[end+1];
sum = max;
}
else
max = sum;
end = i;
}
}
printf("start %d, end %d, sum %d\n", start, end, max);
}
main()
{
int m[10] = {-2,-3,-6,-3,-4,-3,-2,-1,-2,-3};
MaxSum(m, 10);
}
[/code:1:f74f43b509]
| | guile 回复于：2004-12-29 11:51:54
| 我的想法是这样：
1如果全是负数，那么返回值就是最大的那个负数，存到sum
2当遇到正数时，就考虑求和sum1。一直求到最后一个正数，
3但是当后面第二个正数大于后面第一个非正数的绝对值，就把这两个数加到sum1，然后走到第2步。否则，4
4sum1和sum比较，看是否要更改。
代码实现如下
[code:1:52292c0cf9]
#include<iostream>
using namespace std;
void MaxSum(int* ip,int size)
{
int sum=ip[0],sum1=sum,start=0,end=0,start1,end1;
int i=0;
while(ip[i]<0&&i<size)
{
if(ip[i]>sum)
{
sum=ip[i];
start=end=i;
}
}
while(i<size)
{
if(ip[i]>0)
{
start1=end1=i;
sum1=0;
while((end1<size)&&(ip[end1]>0))
{
sum1+=ip[end1];
end1++;
i=end1+1;
if((ip[end1]<=0)&&(end1<size-1)&&(ip[end1+1]>-ip[end1]))
{
sum1+=ip[end1]+ip[end1+1];
end1+=2;
}
}
if(sum1>sum)
{
start=start1;
end=end1-1;
sum=sum1;
}
}
else
{
i++;
}
}
cout<<"Start: "<<start<<endl
<<"End: "<<end<<endl;
for(i=start;i<end;i++)
cout<<ip[i]<<" ";
cout<<endl
<<"The sum is "<<sum<<endl;
}
int main()
{
int a[]={2,3,-6,3,4,3,-2,5,2,-3};
MaxSum(a,10);
return 0;
}[/code:1:52292c0cf9]
| | liulang0808 回复于：2004-12-29 11:52:46
| 强
| | guile 回复于：2004-12-29 11:54:54
| 虽然上面的代码看上去循环有嵌套，不过还是O(n)的算法，内循环改变的也是外循环的i
另外i和end1两个变量其实可以合并，不过为了容易阅读一点，还是多用了一个变量
| | guile 回复于：2004-12-29 12:13:09
| [quote:e95629880a="guile"][/quote:e95629880a]
不行，发现自己第三步考虑太简单了，等我改改
| | assiss 回复于：2004-12-29 12:50:06
| [code:1:1c062cd504]
#include <stdio.h>
#include <stdlib.h>
void MaxSum(int *m, int n)
{
int i, start=0, end=0, max, sum, istart=0, iend=0, sum2=0, start2=0;
max=m[0];
for(i=0;i<n && m[i]<=0;i++)//我觉得把负数单独拿出来考虑更好一点
{
if(m[i]>max)
{
max=m[i];
start=i;
}
}
if(i==n)
{
printf("start %d, end %d, sum %d\n", start, start, max);
return;
}
start2=start=istart=i;
for(i=n-1;i >-1 && m[i]<=0;i--);//末尾的非正数也拿掉,少做几次加法
iend=i;
max=m[start];
sum=0;
for(i=istart;i<=iend;i++)
{
sum+=m[i];
sum2+=m[i];
if(sum>max)
{
end=i;
max=sum;
}
if(sum2<=0 && m[i]>0)//这里用的算法和yuxh的一样.真佩服yuxh,算法这方面做得太好了
{
sum2=m[i];
start2=i;
}
if(sum2>max)
{
start=start2;
end=i;
max=sum2;
}
}
printf("start %d, end %d, sum %d\n", start, end, max);
}
int main()
{
int m[10] = {-2,-3,-6,-3,-4,-3,-2,-1,-2,-3};
MaxSum(m, 10);
return 0;
}
[/code:1:1c062cd504]
| | guile 回复于：2004-12-29 12:52:35
| 算法如下
1用sum,start,end储存最大和，开始下标，结束下标。
如果数组里开始遇到的都是负数，那么sum保存的就是最大的负数
2当遇到正数的时候，开始用sum1求和，start1代表开始下标，end1要用来探测所以存储的是结束下标的下一个
求和一直求到遇到非正数或者结束
如果不是正数，探测下一个下标作为开始
3把后面的非正数和sum1加到sum2，再加下一个正数。
如果sum2>=sum1，则用sum2替换sum1，回到2
否则4
4比较sum和sum1，sum1大的话替换掉sum，以后的探测下标从end1-1开始
[code:1:8a5829c53d]#include<iostream>
using namespace std;
void MaxSum(int* ip,int size)
{
int sum=ip[0],sum1,sum2,start=0,end=0,start1,end1;
int i=0;
while(i<size&&ip[i]<0)
{
if(ip[i]>sum)
{
sum=ip[i];
start=end=i;
}
i++;
}
while(i<size)
{
if(ip[i]>0)
{
start1=end1=i;
sum1=0;
while((end1<size)&&(ip[end1]>=0))
{
sum1+=ip[end1];
end1++;
i=end1;
if((i<size)&&(ip[i]<=0))
{
sum2=sum1;
while((i<size)&&(ip[i]<=0))
{
sum2+=ip[i];
i++;
}
if(i<size)
{
sum2+=ip[i];
if(sum1<=sum2)
{
end1=i+1;
sum1=sum2;
}
}
}
}
if(sum1>sum)
{
start=start1;
end=end1-1;
sum=sum1;
}
}
else
{
i++;
}
}
cout<<"Start: "<<start<<endl
<<"End: "<<end<<endl;
for(i=start;i<=end;i++)
cout<<ip[i]<<" ";
cout<<endl
<<"The sum is "<<sum<<endl;
}
int main()
{
int a[]={-2,-3,-6,3,4,-1,-2,5,2,-3};
MaxSum(a,10);
return 0;
}[/code:1:8a5829c53d]
| | yuxh 回复于：2004-12-29 13:01:49
| assiss的程序还有问题呀!
int m[10] = {2,3,-6,3,4,3,-2,5,2,-3};
start 0, end 8, sum 14
| | yuxh 回复于：2004-12-29 13:15:30
| guile的算法也有问题
int a[]={2,3,-4,3,4,3,-2,5,2,-3};
start:3, end:8, sum:15
| | assiss 回复于：2004-12-29 13:15:38
| [quote:7efec39a79="yuxh"],3,-6,3,4,3,-2,5,2,-3};
start 0, end 8, sum 14[/quote:7efec39a79]
sorry,还没完全领会精神就乱发程序了. :oops: :oops: :oops: :oops:
再来,反正脸皮厚
[code:1:7efec39a79]
#include <stdio.h>
#include <stdlib.h>
void MaxSum(int *m, int n)
{
int i, start=0, end=0, max, sum, istart=0, iend=0, sum2=0, start2=0;
max=m[0];
for(i=0;i<n && m[i]<=0;i++)
{
if(m[i]>max)
{
max=m[i];
start=i;
}
}
if(i==n)
{
printf("start %d, end %d, sum %d\n", start, start, max);
return;
}
end=start2=start=istart=i;//加了个END.因为发现如果只有一个正数时END有误.
for(i=n-1;i >-1 && m[i]<=0;i--);
iend=i;
sum2=sum=max=m[start];
for(i=istart+1;i<=iend;i++)
{
sum+=m[i];
sum2+=m[i];
if(sum>max)
{
end=i;
max=sum;
}
if(m[i-1]<=0 && m[i]>0)
{
sum2=m[i];
start2=i;
}
if(sum2>max)
{
start=start2;
end=i;
sum=max=sum2;//这里又修改了.唉.惭愧.
}
}
printf("start %d, end %d, sum %d\n", start, end, max);
}
int main()
{
int m[10] = {2, 3, -6, 3, 4, 3, -2, 5, 2, -3};
MaxSum(m, 10);
return 0;
}
[/code:1:7efec39a79]
| | guile 回复于：2004-12-29 13:25:43
| [quote:6cb4dcb262="yuxh"]4,3,4,3,-2,5,2,-3};
start:3, end:8, sum:15[/quote:6cb4dcb262]
恩，考虑中
| | yuxh 回复于：2004-12-29 13:30:20
| assiss：
if(m[i-1]<=0 && m[i]>0)
{
sum2=m[i];
start2=i;
}
这样子是不行的:-(
int m[10] = {2, 3, -6, 3, 4, 3, -7, 5, 3, -3};
start 3, end 5, sum 10
| | assiss 回复于：2004-12-29 13:35:53
| [quote:90f4e8b31b="yuxh"], 3, -6, 3, 4, 3, -7, 5, 3, -3};
start 3, end 5, sum 10[/quote:90f4e8b31b]
已经改了.嘿嘿.这次速度比你快一点.刚贴出来就看到错了......不过你F5的速度也太快了吧???
| | yuxh 回复于：2004-12-29 13:37:30
| F5是啥东西？
我看你们两个的程序看得累死
:D :D :D
| | assiss 回复于：2004-12-29 13:43:11
| [quote:96778c1ee6="yuxh"]F5是啥东西？
我看你们两个的程序看得累死
:D :D :D[/quote:96778c1ee6]
习惯上把刷新说成"F5",呵呵,当年用IE落下的毛病.
我第一次贴出修改的程序,里面有你说的问题.但我在很短的时间内就修改了,竟然还是让你看到了,嘿嘿,所以说你的F5速度很快.
你的算法功底太强了,怎么学的?我现在设计算法,总会出错,然后一点一点修改,最后得到一个也不知道是不是正确的结果.不知道是不是因为太懒了,不肯从数学角度上考虑这个问题.
| | yuxh 回复于：2004-12-29 13:50:08
| 偶以前数学系的，大学里就学过BASIC
对于复杂一点的问题先在纸上列一下，把数学问题先搞清楚，不要急着写程序，不然出了问题也不知道什么问题，一点一点地改，把别人看出来的问题补掉，但也不明白最后还会不会出问题，这样不好。
| | twen345 回复于：2004-12-29 14:02:44
| [quote:767c48a497="assiss"]
习惯上把刷新说成"F5",呵呵,当年用IE落下的毛病.
我第一次贴出修改的程序,里面有你说的问题.但我在很短的时间内就修改了,竟然还是让你看到了,嘿嘿,所以说你的F5速度很快.
你的算法功底太强了,怎么学的?我现在设计..........[/quote:767c48a497]
nod,yuxh的算法就是厉害！
| | assiss 回复于：2004-12-29 14:08:49
| [quote:f8814efa68="yuxh"]偶以前数学系的，大学里就学过BASIC
对于复杂一点的问题先在纸上列一下，把数学问题先搞清楚，不要急着写程序，不然出了问题也不知道什么问题，一点一点地改，把别人看出来的问题补掉，但也不明白最后还会不会出问�.........[/quote:f8814efa68]受益匪浅啊.数学系出来的就是不一样.做程序果然很有前途.
| | aero 回复于：2004-12-29 15:22:57
| [quote:75ab43f012="assiss"]芤娣饲嘲?.数学系出来的就是不一样.做程序果然很有前途.[/quote:75ab43f012]
嗯，的确，学数学的出来，就是有一种高屋建瓴的感觉。唉，数学俺是学不好了啊。
yuxh的算法的确不错。可是有一个地方没看明白。感觉那个sum1没什么用啊。下面是我用yuxh的算法写的程序。附加了一个笨笨的O(n2)算法做验证。
[code:1:75ab43f012]
#include <stdio.h>
#include <stdlib.h>
int find_max(int ary[], int *p_start, int *p_end, int num);
void test_find_max(int ary[], int num);
int main(void)
{
int *ary, n, i;
int max, start, end;
printf("How many numbers: ");
scanf("%d", &n);
ary = (int *)malloc(n*sizeof(int));
if (!ary) {
perror("ary malloc");
exit(1);
}
printf("Input numbers: ");
for (i = 0; i < n; i++)
scanf("%d", &ary[i]);
max = find_max(ary, &start, &end, n);
printf("max = %d, start = %d, end = %d\n", max, start, end);
test_find_max(ary, n);
exit(0);
}
int find_max(int ary[], int *p_start, int *p_end, int num)
{
int start, end, max, start1, end1, sum, i;
start = end = start1 = end1 = 0;
max = ary[0] > 0 ? ary[0] : 0;
sum = max;
for (i = 1; i < num; i++) {
if (end1 == i-1) {
sum += ary[i];
if (sum > 0) {
end1++;
if (sum > max) {
start = start1;
end = end1;
max = sum;
}
}
}
else {
if (ary[i] >= 0) {
sum = ary[i];
start1 = end1 = i;
}
}
}
*p_start = start;
*p_end = end;
return max;
}
void test_find_max(int ary[], int num)
{
int max, sum, start, end;
int i, j;
max = sum = start = end = 0;
for (i = 0; i < num; i++) {
sum = 0;
for (j = i; j < num; j++) {
sum += ary[j];
if (sum > max) {
max = sum;
start = i;
end = j;
}
}
}
printf("Test result:\n");
printf("max = %d, start = %d, end = %d\n", max, start, end);
return ;
}
[/code:1:75ab43f012]
| | yuxh 回复于：2004-12-29 16:20:32
| aero言之有理，这样的话可以把end1也去掉
[code:1:f3a84e1167]void MaxSum(int *ary, int n)
{
int i, start=0, end=0, start1=0, max, sum;
max=ary[0];
for(i=1;i<n && ary[i]<=0;i++)
{
if(ary[i]>max)
{
max=ary[i];
start=end=i;
}
}
sum = max > 0 ? max : 0 ;
for(; i<n; i++) {
if(ary[i] > 0 && sum <= 0)
start1 = i;
sum += ary[i];
if (sum > max) {
start = start1;
end = i;
max = sum;
}
else if(sum < 0)
sum = 0;
}
printf("start %d, end %d, sum %d\n", start, end, max);
}
main()
{
int m[10] = {2,3,-6,3,4,3,-2,5,2,-3};
MaxSum(m, 10);
}
[/code:1:f3a84e1167]
| | yuxh 回复于：2004-12-29 16:29:18
| 有个错误，上面的程序已更正!
失败!又发现一个错误，上面的程序再次作了更正
| | assiss 回复于：2004-12-29 17:03:31
| 老天啊,yuxh是不是还准备把程序简化到一两行?受不了了,很受伤,很受打击.aero,借个肩膀用一下.哇哇哇................
| | guile 回复于：2004-12-29 22:28:26
| 佩服yuxh的算法，觉得我考虑问题真是含糊不清。
后来把程序又写了一下，先贴了再研究yuxh的程序
[code:1:c280388c1b]#include<iostream>
using std::cout;
using std::endl;
void MaxSum(int* ip,int size)
{
int sum=ip[0],sum1=0,start=0,end=0,start1,end1;
int i=0;
while(i<size&&ip[i]<=0)
{
if(ip[i]>sum)
{
sum=ip[i];
start=end=i;
}
i++;
}
while(i<size)
{
if(ip[i]>0)
{
sum1=ip[i];
start1=end1=i;
if(sum1>sum)
{
sum=sum1;
start=start1;
end=end1;
}
i++;
while((i<size)&&(sum1>0))
{
if(sum1+ip[i]>0)
{
end1=i;
sum1+=ip[i];
if(sum1>sum)
{
sum=sum1;
start=start1;
end=end1;
}
}
else
{
sum1=0;
}
i++;
}
}
else
i++;
}
cout<<"Start: "<<start<<endl
<<"End: "<<end<<endl;
for(i=start;i<=end;i++)
cout<<ip[i]<<" ";
cout<<endl
<<"The sum is "<<sum<<endl;
}
int main()
{
int a[10]={2,-3,4,-3,2,2,-2,1,4,-3};
MaxSum(a,10);
return 0;
}[/code:1:c280388c1b]
| | whpu000625 回复于：2005-01-08 14:22:48
| 呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法,我们要求的算法复杂度是O(n)的
| | aero 回复于：2005-01-08 19:34:07
| yuxh提出的算法不就是O（n）的吗？
| | lisp 回复于：2005-01-08 19:49:48
| [quote:d3f80313e3="whpu000625"]呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法[/quote:d3f80313e3]
呵呵，表示怀疑
| | guile 回复于：2005-01-08 20:02:46
| [quote:f58c1b2c0e="whpu000625"]呵呵,都是牛人啊,听说这个问题提出来20年后才有人给出算法,我们要求的算法复杂度是O(n)的[/quote:f58c1b2c0e]
真的吗？那我心情好受一些，当时我可是本来想自己做出来，想了一下午还是不对，看了yuxh的算法才算弄懂。
总之打击很大，第二天花100多块钱买了两本算法书...这样说的话我便舒心多了，不过更佩服yuxh了
| | assiss 回复于：2005-01-08 20:07:01
| 怎么可能啊。骗小孩的，guile也相信？
| | guile 回复于：2005-01-08 20:22:48
| [quote:c5b75bf7b9="assiss"]怎么可能啊。骗小孩的，guile也相信？[/quote:c5b75bf7b9]
唔，还是等眼见为实。如果whpu000625能给出出处我便信了。
| | cattiger 回复于：2005-01-09 09:47:04
| 阅读了yuxh的算法，改造了一下，使逻辑统一一下：
各位验证一下
[code:1:e286e83fa5]#include <stdio.h>
void MaxSum(int *ary, int n)
{
int i, start=0, end=0, start1=0, max, sum;
max=sum=ary[0];
for(i=1; i<n; i++)
{
if(ary[i] > 0 && sum <= 0)
{
start1 = i;
}
sum += ary[i];
if(sum<0)
{
start1=i;
}
if (sum > max)
{
start = start1;
end = i;
max = sum;
}
else if(sum < 0)
{
sum = 0;
}
}
printf("start %d, end %d, sum %d\n", start, end, max);
}
void main()
{
int m[10] = {2, 3, -6, 3, 4, 3, -7, 5, 3, -3};
MaxSum(m, 10);
return;
}[/code:1:e286e83fa5]
| | eagerly1 回复于：2005-01-09 14:17:57
| [quote:ebc5edec10="cattiger"]
[/quote:ebc5edec10][code:1:ebc5edec10]if(ary[i] > 0 && sum <= 0)
{
start1 = i;
}
sum += ary[i];
[/code:1:ebc5edec10]
似乎应该为：[code:1:ebc5edec10]if(ary[i] > 0 && sum <= 0)
{
start1 = i;
sum=0;
}
sum += ary[i];
[/code:1:ebc5edec10]
| | yuxh 回复于：2005-01-09 17:34:14
| 楼上说得没错
int m[10] = {-3, -1, -6, -3, -4, -3, -7, -2, -3, -3};
所以
[quote:81b92bcdea="assiss"]我觉得把负数单独拿出来考虑更好一点[/quote:81b92bcdea]也是有道理的
| | win_hate 回复于：2005-01-09 23:59:36
| 因为 yuxh 的精彩算法，此贴评为精彩。
| | win_hate 回复于：2005-01-10 00:22:58
| 我对这个问题作一个简单分析：
一串正负(零)交替的数，把相邻的正数合并求和，把相邻的负数也合并求和，零可分到任何一组当中，得到如下的形式:
1) +A_1, -A_2, +A3, -A4, ......
2) -A_1, +A_2, -A3, +A4, ......
先讨论（1）， A_1 记录为当前最大和。如果 A_1 - A_2 <= 0, 则 ，A_1, -A_2 丢弃，从 A_3 重新计算。否则， A_1 - A_2 + A_3 为当前最大和，依此类推。
再讨论 (2) 如果合并后的序列仍有多项，则 －A_1 可丢弃，从 A_2 开始讨论，这样就归结到了情形（1）。如序列中只有一项（原序列非正），可区别对待，相当于序列求最大值。
实现：
出于对效率的考虑，我们不能把 A_i 一一求出，可用如下方法：
a) 如果开始有负数，现求出这段负数（0）的最大值，并记录。
b) 如果序列未结束，用一个临时变量对后面的一段正数（0)求和，并取代原最大值（最后一次取代）。
c) 如果序列仍未结束，把后一段的负数（0）依次加到该临时变量中。一旦这个临时变量为负，则跳过后续的负数，从下一个正数段开始。求和的临时变量设为0。如果把该段负数累加完后，临时变量仍不为负，则可再与其后的正数段相加
......
本人的一个实现：
.h
[code:1:d4a9ffccfa]
struct lms {
int l;
int r;
int sum;
};
[/code:1:d4a9ffccfa]
.c
[code:1:d4a9ffccfa]
void lms(int *tag, int len, struct lms *info)
{
int sum, tmp, r, l = 0;
for (r = 0; tag[r] <= 0 && r < len; r++) {
l = (tag[l] < tag[r]) ? r : l;
}
info->l = info->r = l;
info->sum = tag[info->l];
l = r;
sum = 0;
while (r < len) {
for (; r < len && tag[r] >= 0; r++)
sum += tag[r];
if (sum > info->sum) {
info->sum = sum;
info->l = l;
info->r = r - 1;
}
for (; r < len && tag[r] <= 0; r++) {
if ((sum += tag[r]) < 0) {
for (; r < len && tag[r] <= 0; r++);
if (r < len) {
sum = 0;
l = r;
}
r--;
}
}
}
}
[/code:1:d4a9ffccfa]
| | feingnord 回复于：2005-01-10 03:23:03
| 如果两个相邻元素是最大的，那和肯定是最大的，这么考虑so simple,
但是相邻这个概念就太模糊，就像二楼恩个一块相邻那种理解也说得过去，
但是超过两个，其中某些元素说自己和其它元素都相邻，揍有点不大对劲。
这种出题方式会把一些逻辑严密思维清晰的人给整死的。嘿嘿
| | ericooler 回复于：2005-01-13 11:45:08
| 看到此帖，花了一个多小时想出了算法，刚要发帖，发现win_hate已经贴出来了，那就顶一下了。 :em11:
| | win_hate 回复于：2005-01-13 11:58:25
| [quote:97e96fa894="ericooler"]看到此帖，花了一个多小时想出了算法，刚要发帖，发现win_hate已经贴出来了，那就顶一下了。 :em11:[/quote:97e96fa894]
我贴出来的是 yuxh 的算法，不是我想出来的。
| | cattiger 回复于：2005-01-13 12:17:25
| [code:1:59c251eeee]#include <stdio.h>
void MaxSum(int *ary, int n)
{
int i, start=0, end=0, start1=0, max, sum;
max=sum=ary[0];
for(i=1; i<n; i++)
{
if(sum < 0)
{
sum = 0;
}
if((sum==0&&ary[i]>0)||ary[i]>max)
{
start1=i;
}
sum += ary[i];
if (sum > max)
{
start = start1;
end = i;
max = sum;
}
}
printf("start %d, end %d, sum %d\n", start, end, max);
}
void main()
{
int m[10] ={-2,-3,-6,-3,-4,-3,-2,-1,-2,-3};//{2,3,-6,3,4,3,-2,5,2,-3}; // {-3, -1, -6, 0, -4, -3, -7, -2, -3, -3};//
MaxSum(m, 10);
return;
}[/code:1:59c251eeee]
| | eagerly1 回复于：2005-01-13 18:15:48
| [quote:95f5a89724]一旦这个临时变量为负，则跳过后续的负数，从下一个正数段开始。[/quote:95f5a89724]
这样一来，起点就会失去吧。除非判断时记录
| | zouyuchong 回复于：2005-07-31 18:59:20
| 用线段树做
或者转换成RMQ问题
| | sasnzy12 回复于：2005-08-06 20:47:53
| 比较简单的贪心吧~~（如果贪心不能理解的话 用动态规划好了）
贪心就是把正数与正数合并 负数与负数合并 如果是0就不要
形成一个交错数列 （该数列头尾必须是正数，如果是负数则删除）
然后从头开始 //result是合并以后的交错数列
max=result[0]; (result[0]是正数,result[result.size()-1]也是正数
for (int i=2;i<result.size()-2;i+=2)
max=(result[i]>max+result[i-1]+result[i] ? result[i] : max+result[i-1]+result[i]) //OK
cout<<max<<endl;
贪心 o(N) （编程相对复杂）
动态规划O(N^2) （10代码行解决问题）
居然还要线段树 ？ %#$%#$%#
| |
|
