| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 495 人关注过本帖
标题:大家 看看这个问题 的解法对吗?
只看楼主 加入收藏
edward9092
Rank: 2
等 级:等待验证会员
帖 子:329
专家分:59
注 册:2009-1-5
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:5 
大家 看看这个问题 的解法对吗?
问题描述:

从文件in.txt中输入一组数据,  然后求 这组数据中的连着的最大的和.


程序代码:
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
    ifstream in("in.txt");
    int n;
    in>>n;
    int *a=new int[n];
    int *sum=new int[n];
    
    int end=0,begin=n-1;
    for(int i=0;i<n;i++)
        in>>a[i];
    sum[0]=a[0];

    int max_sum=sum[0];
    for(i=1;i<n;i++)//找到后界限
    {
        sum[i]=sum[i-1]+a[i];
        if(sum[i]>max_sum)
        {
            max_sum=sum[i];
            end=i;
        }
    }
    cout<<"向后遍历得到的sum:"<<endl;
    for(i=0;i<n;i++)
        cout<<sum[i]<<"\t";
    cout<<endl<<endl;;
    sum[n-1]=a[n-1];
    max_sum=a[n-1];
    for(i=n-2;i>=0;i--)//向前找到前界限
    {
        sum[i]=sum[i+1]+a[i];
        if(sum[i]>max_sum)
        {
            max_sum=sum[i];
            begin=i;
        }
    }
    cout<<"原数据:"<<endl;
    for(i=0;i<n;i++)
        cout<<a[i]<<"\t";
    cout<<endl<<endl;
    cout<<"向前遍历得到的sum:"<<endl;
    for(i=0;i<n;i++)
        cout<<sum[i]<<"\t";
    cout<<endl<<endl;

    cout<<"begin="<<begin<<"\t"<<"end="<<end<<endl;
    max_sum=0;
    for(i=begin;i<=end;i++)
    {
        cout<<a[i]<<"\t";
        max_sum+=a[i];
    }
    cout<<endl<<"max_sum="<<max_sum<<endl;
    return 0;
}


先谢谢了

   
搜索更多相关主题的帖子: 解法 
2009-09-18 12:36
edward9092
Rank: 2
等 级:等待验证会员
帖 子:329
专家分:59
注 册:2009-1-5
收藏
得分:0 
自己顶...

高手 帮帮忙了.

知道有个DP算法.

但是不会,自己写的这个高手指点一下啦.
2009-09-18 23:17
whyming
Rank: 2
等 级:论坛游民
帖 子:2
专家分:14
注 册:2009-9-19
收藏
得分:14 
楼主这个算法好像没什么问题,而且以前都没见过,挺好的,算法复杂度也不高,就是代码太复杂了。
那个DP算法我在书上见过,给你贴个函数分享下

int MaxSum(int n,int a) //n为数组大小,a就是数组
{
   int sum=0,b=0;
   for(int i=0;i<n;i++)
       {
         if(b>0) b+=a[i];
         else b=a[i]
         if(b>sum) sum=b;
        }
return sum;
}
2009-09-19 11:17
whyming
Rank: 2
等 级:论坛游民
帖 子:2
专家分:14
注 册:2009-9-19
收藏
得分:0 
不对不对,楼主的算法还是有问题,如果遇到数组中间有一个特大负数的时候会导致begin比end大。
2009-09-19 11:26
edward9092
Rank: 2
等 级:等待验证会员
帖 子:329
专家分:59
注 册:2009-1-5
收藏
得分:0 
以下是引用whyming在2009-9-19 11:26的发言:

不对不对,楼主的算法还是有问题,如果遇到数组中间有一个特大负数的时候会导致begin比end大。


应该不会吧..........
2009-09-22 22:42
edward9092
Rank: 2
等 级:等待验证会员
帖 子:329
专家分:59
注 册:2009-1-5
收藏
得分:0 
只是有个问题  如果数据中全部都是负数,就会有错..

大家帮忙改一下........
2009-09-22 22:43
快速回复:大家 看看这个问题 的解法对吗?
数据加载中...
 
   



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

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