最大子段和问题(C/C++)

Description

给定有n个整数(可能为负整数)组成的序列a1,a2,...,an,求该序列连续的子段和的最大值。如果该子段的所有元素和是负整数时定义其最大子段和为0。

Input

第一行有一个正整数n(n<1000)，后面跟n个整数,绝对值都小于10000。直到文件结束。

Output

输出它的最大子段和。

Sample Input

6 -2 11 -4 13 -5 -2

Sample Output

参考: https://blog.csdn.net/niteip/article/details/7444973#

穷举法 时间复杂度：$O(n^3)$

/*O(n^3)*/

#include <stdio.h>

#include <stdlib.h>

int main()

{

    int n;

    int num[1001];

    int i, j, k;

    int sum, max;

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

    {

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

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

        max = 0;

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

        {

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

            {

                sum = 0;

                for (k = i; k <= j; k++)

                    sum += num[k];

                if (sum > max)

                    max = sum;

            }

        }

        printf("%d\n", max);

    }

    return 0;

}

穷举法

时间复杂度：$O(n^2)$

/*O(n^2)*/

#include <stdio.h>

#include <stdlib.h>

int main()

{

    int n;

    int num[1001];

    int i, j, k;

    int sum, max;

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

    {

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

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

        max = 0;

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

        {

            sum = 0;

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

            {

                sum += num[j];

                if (sum > max)

                    max = sum;

            }

        }

        printf("%d\n", max);

    }

    return 0;

}

分治法

时间复杂度：$O(nlog_2n)$

/*O(nlogn)分治法*/

#include <iostream>

#include <cstdio>

#include <cstdlib>

int maxSubSegSum(int num[], int left, int right)

{

    int mid = (left + right) / 2;

    if (left == right)

        return num[left] > 0 ? num[left] : 0;

    int leftMaxSum = maxSubSegSum(num, left, mid);

    int rightMaxSum = maxSubSegSum(num, mid + 1, right);

    int sum = 0;

    int leftSum = 0;

    for (int i = mid; i >= left; i--)

    {

        sum += num[i];

        if (sum > leftSum)

            leftSum = sum;

    }

    sum = 0;

    int rightSum = 0;

    for (int i = mid + 1; i <= right; i++)

    {

        sum += num[i];

        if (sum > rightSum)

            rightSum = sum;

    }

    int retSum = leftSum + rightSum;

    if (retSum < leftMaxSum)

        retSum = leftMaxSum;

    if (retSum < rightMaxSum)

        retSum = rightMaxSum;

    return retSum;

}

int main()

{

    int n;

    int num[1001];

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

    {

        for (int i = 0; i < n; i++)

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

        printf("%d\n", maxSubSegSum(num, 0, n - 1));

    }

    return 0;

}

动态规划

时间复杂度：$O(n)$

/*O(n) 动态规划*/

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

int main()

{

    int n;

    int num[1001];

    int f[1001 + 1];

    int i;

    int max;

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

    {

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

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

        max = 0;

        memset(f, 0, sizeof(f));

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

        {

            if (f[i - 1] > 0)

                f[i] = f[i - 1] + num[i];

            else

                f[i] = num[i];

            if (f[i] > max)

                max = f[i];

        }

        printf("%d\n", max);

    }

    return 0;

}

或者

/*O(n) 动态规划*/

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

int main()

{

    int n;

    int num[1001];

    int b;

    int i;

    int max;

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

    {

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

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

        max = 0;

        b = 0;

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

        {

            b = b > 0 ? b + num[i] : num[i];

            max = b > max ? b : max;

        }

        printf("%d\n", max);

    }

    return 0;

}

巴特西