注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

火车的家

Put first thing first

 
 
 

日志

 
 

2016.06.15 求连续子数组的最大和  

2016-06-15 16:45:31|  分类: 技术博客 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

输入一个整型数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。
#include <stdlib.h>
#include <stdio.h>

#define SUM 10
#define max( v1 , v2 ) ( v1>v2 ? v1 : v2 )

int cal( int * p_array, int size )
{
        int i = 0;
        int result = 0;
        int * sum = malloc(size*sizeof(int));

        if ( size == 1 ) {
                result = p_array[0];
                goto end;
        }

        sum[0] = p_array[0];
        result = sum[0];
        for ( i=1; i<size; ++i ) {
                sum[i] = max(sum[i-1] + p_array[i], p_array[i]);

                if ( result < sum[i] ) {
                        result = sum[i];
                }
        }

end:
        free(sum);
        return result;
}

int main( int argc, char * argv[] )
{
        int i = 0;
        int test[SUM] = {0, -1, 12, -8, 11, 12, 99, -200, 20, -50};

        printf("array= ");
        for ( i=0; i<SUM; ++i ) {
                printf("%d,", test[i]);
        }
        printf("\n");

        printf("cal result = %d\n", cal(test, SUM));

        return 0;
}

  评论这张
 
阅读(122)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017