求最小的正子序列和（纯C语言实现）

代码实现

#include <stdio.h>
#include <malloc.h>
#include <string.h>

struct Node
{
    int sum;
    int pos;
};
//返回值：0 - node1>node2，1 - node1<node2
int cmp(struct Node *node1, struct Node *node2)
{
    if(node1->sum == node2->sum)
    {
        return node1->pos < node2->pos;
    }
    return node1->sum < node2->sum;
}
//快速排序算法
void Qsort(struct Node *node, int bgn, int end, int (*ptr)(struct Node *, struct Node *))
{
    struct Node baseN;
    int left = bgn;
    int right = end;

    //对基准点赋值
    baseN.sum = node[bgn].sum;
    baseN.pos = node[bgn].pos;

    //递归结束
    if(bgn >= end)
    {
        return;
    }

    while(left < right)
    {
        while((left < right) && (ptr(&node[right], &baseN) == 0))
        {
            right --;
        }
        //发现小于baseN的点，放到左边
        if(left < right)
        {
            memcpy(&node[left], &node[right], sizeof(struct Node));
            left++;
        }

        while((left < right) && (ptr(&node[left], &baseN) == 1))
        {
            left++;
        }
        //发现大于baseN的点，放到右边
        if(left < right)
        {
            memcpy(&node[right], &node[left], sizeof(struct Node));
            right--;
        }
    }
    //将基准点放到相遇点
    memcpy(&node[left], &baseN, sizeof(struct Node));

    //对左边递归
    Qsort(node, bgn, left-1, ptr);
    //对右边递归
    Qsort(node, left+1, end, ptr);
}
int minseqpstsum(int *arr, int len)
{
    /***
    //下面这种网上广为流传的做法有严重的bug：如果前面的序列是递增的，后面的则都是负数，会触发bug
    //如：4 5 6 -1 -2
    int minsum = 0xFFFF;
    int tmpsum = 0;
    int i = 0;
    for(i = 0; i < len; i++)
    {
        tmpsum += arr[i];
        if((tmpsum <= minsum) && (tmpsum > 0))
        {
            minsum = tmpsum;
        }
        if(tmpsum > minsum)
        {
            tmpsum = 0;
        }
    }
    ***/

    struct Node node[50005];
    int i = 0;
    //minsum存放最终结果
    int minsum = -1;
    int tempsum = 0;
    int flag = 0;

    node[0].sum = 0;
    node[0].pos = 0;

    //将值赋到每个节点中
    for(i = 0; i < len; i++)
    {
        tempsum = tempsum + arr[i];
        node[i+1].sum = tempsum;
        node[i+1].pos = i+1;
    }
    //快排
    Qsort(node, 0, len, cmp);

    //获取到最小正子序列和
    for(i = 1; i <= len; i++)
    {
        if((node[i].sum > node[i-1].sum) && (node[i].pos > node[i-1].pos))
        {
            //如果是第一次，则赋初始值
            if(flag == 0)
            {
                flag = 1;
                minsum = node[i].sum - node[i-1].sum;
            }
            else
            {
                if(node[i].sum -node[i-1].sum < minsum)
                {
                    minsum = node[i].sum - node[i-1].sum;
                }
            }
        }
    }
    return minsum;
}
int main(int argc, char *argv[])
{
    int *arr = NULL;
    int len = 0;
    int i = 0;
    int minsum = 0;

    printf("输入数组长度：");
    scanf("%d", &len);
    arr = (int *)malloc(sizeof(int) * len);
    printf("输入数组元素：");
    for(i = 0; i < len; i++)
    {
        scanf("%d", &arr[i]);
    }

    minsum = minseqpstsum(arr, len);
    printf("最小的正子序列和 = [%d]\n", minsum);

    free(arr);
    return 0;
}

编译

gcc -o minpossum minpossum.c -g

测试案例

4, 0, 4, -1, -1
4,-1,6,-2,-1,3,6,-2

运行截图

运行结果.png

参考案例

这个里面有详细的原理

2019年6月9日