HEIMIIY
2018-06-03 07:34
采纳率: 61.1%
浏览 1.7k
已采纳

c语言编译的最大子序列求和问题

定(可能有负数)整数序列A1, A2, A3..., An,求这个序列中子序列和的最大值。(为方便起见,如果所有整数均为负数,则最大子序列和为0)。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

13条回答 默认 最新

  • 小哈里 2018-06-08 00:18
    已采纳
    1. 代码已全部改成C风格,
    2. 代码已C测试通过
    3. 已经加上题解和思路
    4. 又不会可以记叙文

    可以参考我的:https://blog.csdn.net/qq_33957603/article/details/80554648

    以及代码提交(验证正确)地址:http://www.joyoi.cn/problem/tyvj-1305

    ###传统的做法是,枚举(只要对的话就够了
    如果n<=10^3,我们很容易写出枚举(s是前缀和,区间[l,r]的和就是s[r]-s[l-1]。枚举l,r即可。

     #include<stdio.h>
    #define maxn 300010
    #define max(a,b) (a>b?a:b)
    int a[maxn], q[maxn];
    long long s[maxn], ans;
    int main(){
        int n, m;
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++){
            scanf("%d",&a[i]);  s[i]=s[i-1]+a[i];
        }
        for(int i = 1; i <= m; i++)//枚举长度
            for(int j = i; j <= n; j++)//枚举r
                ans = max(ans, s[j]-s[j-i]);//可以算出l
        printf("%d\n",ans);
        return 0;
    }
    

    ###如果需要更快的,,,可以考虑用单调队列

    • 如果右端点是i,那么就转为求一个左端点j属于[i-m,i-1]并且s[j]最小。并且j越靠近m一定是越优的(在后面更不容易超过m。
    • 所以选择集合一定是,“下标位置递增,对应前缀和s也递增”的序列,我们可以用队列保存这个序列。
    #include<stdio.h>
    #define max(a,b) (a>b?a:b)
    #define maxn 300010
    using namespace std;
    int a[maxn], q[maxn];
    long long s[maxn], ans;
    int main(){
        int n, m;
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++){
            scanf("%d",&a[i]);  s[i]=s[i-1]+a[i];
        }
        int l = 1, r = 1;
        q[l] = 0; //save j
        for(int i = 1; i <= n; i++){
            while(l<=r && q[l]<i-m)l++;
            ans = max(ans, s[i]-s[q[l]]);
            while(l<=r && s[q[r]]>s[i])r--;
            q[++r] = i;
        }
        printf("%d\n",ans);
        return 0;
    }
    
    点赞 评论
  • tianchangsu5948 2018-06-03 08:05

    include 'stdio.h'
    int max(int *a){
    int sum = 0
    for(int i = 0;i if(sum sum = 0;
    if(a[i]>0){
    sum+=a[i];
    }

    }
            return sum;
    }
    
    点赞 评论
  • blownewbee 2018-06-03 08:10

    参考这个程序 https://blog.csdn.net/linux_ever/article/details/50464947
    c语言只要把输入输出换成scanf printf即可。

    点赞 评论
  • sinat_34360643 2018-06-03 08:21

    int maxSubArray(vector& nums) {
    int size=nums.size();
    int sum=0;
    int max=(-2147483647-1);

        for(int i=0;i<size;++i){
            sum+=nums[i];
            if(max<sum){
                max=sum;
            }
            if(sum<0){
                sum=0;
            }
        }
        return max;
    }
    
    点赞 评论
  • qq_19868385 2018-06-03 08:31

    include 'stdio.h'
    int max(int *a){
    int sum = 0
    for(int i = 0;i if(sum sum = 0;
    if(a[i]>0){
    sum+=a[i];
    }

    }
    return sum;
    }

    点赞 评论
  • zwj1234_ 2018-06-03 09:06
    点赞 评论
  • weixin_42190769 2018-06-03 09:11

    int MaxSubsequenceSum( const int A[],int N)
    {
    int ThisSum,MaxSum,i;
    ThisSum=0;
    MaxSum=0;
    for(i=0;i ThisSum+=A[i];
    if(ThisSum>MaxSum){
    MaxSum=ThuisSum;
    }else if(ThisSum<0){
    ThisSum=0;}}
    retu}rn Maxsum;

    点赞 评论
  • zy1306 2018-06-03 10:00

    方法有很多,效率比较高的是分治法(O(nlogn))和动态规划法(O(n))。
    动态规划法:

     int MaxSum(int *arr, int n)
    {
        int sum = 0, b = 0;
        for (int i = 0; i < n; i++)
        {
            if (b > 0)
                b += arr[i];
            else
                b = arr[i];
            if (b > sum)
                sum = b;
        }
        return sum;
    }
    
    点赞 评论
  • KB2095 2018-06-03 10:04

    #include
    #include

    long seriesMaxSum(int *series, size_t n);

    void main(size_t argc, char **argv) {
    if (argc > 1) {
    int *series;
    size_t counter;

        if (!(series = malloc((argc - 1) * sizeof(int)))) {
            fprintf(stderr, "Out of memory...\n");
            return;
        }
    
        for (counter = 1; counter < argc; counter++) 
            *(series + (counter - 1)) = atoi(argv[counter]);
    
        printf("The biggest sum in the series is: %ld\n", seriesMaxSum(series, argc - 1));
    } else
        printf("<Usage>: ./%20s [series]\nExample: ./%20s (\\d+\\s)+\n", argv[0], argv[0]);
    

    }

    long seriesMaxSum(int *series, size_t n) {
    long partialSum = 0, biggestSum = 0;
    size_t index;

    for (index = 0; index < n; index++) {
        if ((partialSum + series[index]) >= partialSum) {
            if ((partialSum += series[index]) >= biggestSum)
                biggestSum = partialSum;
        } else
            partialSum = 0;
    }
    
    return biggestSum;
    

    }

    点赞 评论
  • Messi-hack 2018-06-03 10:15

    1.1 分解:这个数组只能出现在三个位置:从中间分,要么完全在左边,要么完全在右边,要么穿过中间,所以分三部分求最大
    1.2 求解:如果在左边或右边继续分,最后只剩一个数返回,对于穿过中间的,分成两部分求最大,每次都如此。
    1.3 组合:每次返回左边,右边,中间这三个中最大的
    class Solution {
    public int maxSubArray(int[] nums) {
    return findMax(nums,0,nums.length-1);
    }
    public static int findMax(int []num,int left,int right){
    if (left>=right)return num[left];
    int mid=(left+right)/2;
    //寻找左边最大
    int lmax=findMax(num,left,mid-1);
    //寻找右边最大
    int rmax=findMax(num,mid+1,right);
    //寻找中间最大,并分成两部分,找从中间左边连续最大,中间到右边连续最大,最后加起来
    int mmax=num[mid],t=mmax;
    for (int i=mid-1;i>=left;i--){
    t+=num[i];
    mmax=Math.max(mmax,t);
    }
    t=mmax;
    for (int i=mid+1; i<=right; i++){
    t+=num[i];
    mmax=Math.max(mmax,t);
    }
    //合并
    return Math.max(mmax,Math.max(lmax,rmax));
    }
    }

    点赞 评论
  • 不镜 2018-06-03 10:33

    求最大的子序列和问题
    给定整数A1,A2,....An,....(可能有负数),求该数据序列的最大子序列的和。
    比如:输入-2, 11, -4, 13, -5, -2; 答案是20(11,-4,13三个连续数字的和)

    我们遍历一次数据序列,当每次的this_sum大于最大值的时候就更新max_sum的值。当this_sum小于0的时候,就把它置为0,再从当前位置开始计算(每次求和的结果小于0,就从下一个数据开始求和)。还有一点要清楚,最大序列的第一个数字不可能小于0。可以看出该算法的时间复杂度是O(n);
    该问题还有其它几种时间复杂度比较高的算法。具体看:数据结构与算法分析C++描述(2.3章节)

    [cpp] view plain copy
    /*************************************************************************
    > File Name: max_seq_sum.cpp
    > Author:

    > Mail:

    > Created Time: 2016年01月05日 星期二 19时49分30秒
    ************************************************************************/

    #include

    #include

    using namespace std;

    void input_data(vector & data)

    {

    int tmp;

    cout << "输入数据序列:" << endl;  
    while(cin >> tmp){  
        data.push_back(tmp);  
    }  
    

    }

    void output_data(vector & data)

    {

    cout << "输入的数据序列:" << endl;

    for (int i = 0; i < data.size(); ++i)

    cout << data[i] << " ";

    cout << endl;

    }

    int max_seq_sum(vector & data)

    {

    int max_sum = 0, this_sum = 0;

    for (int i = 0; i < data.size(); ++i){

    this_sum += data[i];

        if(this_sum > max_sum)  
            max_sum = this_sum;  
        else if(this_sum < 0)  
            this_sum = 0;  
    }  
    return max_sum;  
    

    }

    int main()

    {

    vector data;

    //输入数据

    input_data(data);

    output_data(data);  
    
    cout << "最大序列的值是: ";  
    cout << max_seq_sum(data) << endl;  
    
    return 0;  
    

    }

    点赞 评论
  • 大佬离我多远 2018-06-04 02:22

    include

    int main(void)

    {

    int n, a[100001];

    while (~ scanf("%d", &n))

    {

    int i;

    for (i = 1; i <= n; i ++)

    scanf("%d", &a[i]);

    int sum = a[1], min = a[1]; // 初始值

    for (i =2; i <= n; i ++)

    {

    if (sum <= 0)

    sum = a[i]; // 如果前面位置最大连续子序列和小于0, 就讲此时的位置的值记录下来

    else

    sum += a[i]; // 如果大于0, 就继续相加。

            if (sum > min)   
                min = sum;  
         }   
         printf("%d\n", min);   
    }  
    return 0;      
    

    }

    这个如果输入的是
    5
    -1 -2 -3 -4 -5
    输出的是-1
    你可以加一个循环判断 如果都是负的话 输出0即可

    点赞 评论
  • weixin_42342461 2018-06-04 02:55

    另外命名一个数组b[n],当An为正数计入b[n],因为为负数时2求和值会变小,所以只累计大于0的数,只需要将b[n]求和就可以了。
    #include 'stdio.h'
    int Max(int n, int *b)
    {
    int m=0, sum=0;//设m为求和中间变量
    int i;
    for(i=0; i {
    if (m>0)
    m+=b[i];
    else
    m=b[i];
    if(m>=sum)
    sum=m;
    else
    sum=0;
    }
    return sum;
    }

    点赞 评论

相关推荐 更多相似问题