专栏首页开发与安全算法:Solutions for the Maximum Subsequence Sum Problem

算法:Solutions for the Maximum Subsequence Sum Problem

The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. --from wiki

下面我们分析四种算法的时间性能,由于运行时间相差较大,我们分成两组进行对比:

环境:ubuntu 12.04

时间单位:ms

时间性能:presume that the input is preread

第一组:输入数据元素个数2000

/*************************************************************************
    > File Name: algorithm1.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: 2012年12月24日 星期一 22时41分56秒
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<sys/time.h>

int maxsubsum1(const int a[], int n)
{
    int thissum, maxsum, i, j, k;

    maxsum = 0;
    for (i = 0; i < n; i++)
    {
        for (j = i; j < n; j++)
        {
            thissum = 0;
            for (k = i; k <= j; k++)
                thissum += a[k];

            if (thissum > maxsum)
                maxsum = thissum;
        }
    }
    return maxsum;
}

int maxsubsum2(const int a[], int n)
{
    int thissum, maxsum, i, j;

    maxsum = 0;
    for (i = 0; i < n; i++)
    {
        thissum = 0;
        for (j = i; j < n; j++)
        {
            thissum += a[j];

            if (thissum > maxsum)
                maxsum = thissum;
        }
    }
    return maxsum;
}

long GetTickCount(void)
{
    struct timeval tv;

    gettimeofday(&tv, NULL);

    return (tv.tv_sec * 1000 + tv.tv_usec / 1000);
}

int main(void)
{
    int i, n = 2000;
    int *ptr = malloc(sizeof(int) * n);
    srand(time(NULL));
    for (i = 0; i < n; i++)
        ptr[i] = rand() % 50 - 25;
    // adopt algorithm  1
    unsigned int utimecost = GetTickCount();
    int result = maxsubsum1(ptr, n);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

    // adopt algorithm  2
    utimecost = GetTickCount();
    result = maxsubsum2(ptr, n);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

    free(ptr);

    return 0;
}

输出为:

max subsequence sum is 275, time cost 4423 max subsequence sum is 275, time cost 6

第二组:输入数据元素个数 1000000

/*************************************************************************
    > File Name: divide_conquer.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: 2012年12月24日 星期一 23时24分41秒
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include <sys/time.h> /* struct timeval, gettimeofday(), struct itimerval, setitimer(), ITIMER_REAL */

int divide_conquer(int arr[], int start, int end)
{
    if(start == end)
        return (arr[start] > 0 ? arr[start] : 0);

    int mid = (start + end) / 2;
    int max_left = divide_conquer(arr, start, mid);
    int max_right = divide_conquer(arr, mid + 1, end);
    // mid subsequence

    int max_left_border = 0;
    int tmp_sum = 0;
    int i;

    for(i = mid; i >= start; i--)
    {
        tmp_sum += arr[i];
        if(tmp_sum > max_left_border)
            max_left_border = tmp_sum;
    }

    int max_right_border = 0;
    tmp_sum = 0;
    for(i = mid + 1; i <= end; i++)
    {
        tmp_sum += arr[i];
        if(tmp_sum > max_right_border)
            max_right_border = tmp_sum;
    }

    int max_mid = max_left_border + max_right_border;
    // max subsequence
    int iresult = max_left;
    if(max_right > iresult)
        iresult = max_right;
    if(max_mid > iresult)
        iresult = max_mid;
    return iresult;
}

int maxsubsum3(const int a[], int n)
{
    int j, thissum, maxsum;
    thissum = maxsum = 0;
    for (j = 0; j < n; j++)
    {
        thissum += a[j];

        if (thissum > maxsum)
            maxsum = thissum;
        else if (thissum < 0)
            thissum = 0;
    }

    return maxsum;
}

long GetTickCount(void)
{
    struct timeval tv;

    gettimeofday(&tv, NULL);

    return (tv.tv_sec * 1000 + tv.tv_usec / 1000);
}

int main(void)
{
    int i, n = 1000000;
    int *ptr = malloc(sizeof(int) * n);
    srand(time(NULL));
    for (i = 0; i < n; i++)
        ptr[i] = rand() % 50 - 25;
    // adopt divide_conquer algorithm
    unsigned int utimecost = GetTickCount();
    int result = divide_conquer(ptr, 0, n - 1);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);
    // adopt algorithm 3
    utimecost = GetTickCount();
    result = maxsubsum3(ptr, n);
    utimecost = GetTickCount() - utimecost;
    printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

    free(ptr);

    return 0;
}

输出为:

max subsequence sum is 2410, time cost 217 max subsequence sum is 2410, time cost 4

分析:

在《data structure and algorithm analysis in c》中有对这四种算法时间性能的分析,依次下来分别是O(n^3),O(n^2),O(nlogn),O(n),即使我们在第二组输入的元素个数是第一组的500倍,第二组的运行时间都要比第一组的小。下图2-2是作者写书时测试的时间列表,显然现在的机器运行得更快。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • linux系统编程之信号(五):实时信号与sigqueue函数

    一、sigqueue函数 功能:新的发送信号系统调用,主要是针对实时信号提出的支持信号带有参数,与函数sigaction()配合使用。 原型:int sigqu...

    s1mba
  • 从零开始学C++之模板(三):缺省模板参数(借助标准模板容器实现Stack模板)、成员模板、关键字typename

    一、缺省模板参数 回顾前面的文章,都是自己管理stack的内存,无论是链栈还是数组栈,能否借助标准模板容器管理呢?答案是肯定的,只需要多传一个模板参数即可,而且...

    s1mba
  • 散列表(一):散列表概念、 散列函数构造方法、 常见字符串哈希函数(测试冲突)

    一、散列表基本概念 1、散列表(hash table) ,也叫哈希表,是根据关键码而直接进行访问的数据结构。也就是说,它通过把关键码映射到表中一个位置 来访问记...

    s1mba
  • 历届试题 大臣的旅费

    问题描述 很久以前,T王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。

    AI那点小事
  • 前m大的数(堆)- HDU 1280

    还记得Gardon给小希布置的那个作业么?(上次比赛的1005)其实小希已经找回了原来的那张数表,现在她想确认一下她的答案是否正确,但是整个的答案是很庞大的表,...

    ACM算法日常
  • 1212 最大公约数

    1212 最大公约数  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 白银 Silver 题目描述 Description 求两个数A和...

    attack
  • 小白详细讲解快速幂--杭电oj2035-A^B

    输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

    用户2038589
  • 最小生成树(Prim算法和Kruskal算法算法详解)

    通俗易懂的讲就是最小生成树包含原图的所有节点而只用最少的边和最小的权值距离。因为n个节点最少需要n-1个边联通,而距离就需要采取某种策略选择恰当的边。

    bigsai
  • 蓝桥杯 大臣的旅费

    做过相同类型的题 题意就是求树的直径,即树中任意两点之间带权路径和的最大值。 思路就是用两次BFS,第一次搜到直径的一端,第二次就直接计算直径的长度。至于为啥是...

    用户1148523
  • [golang][hugo]使用Hugo搭建静态站点

    hugo下载地址:https://github.com/gohugoio/hugo

    landv

扫码关注云+社区

领取腾讯云代金券