2022年阅读书单

本文目录

1. 1、算法描述
2. 2、C编程实现
3. THE END!

1、算法描述

输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如:
输入的数组为1,-2,3,10,-4,7,2,-5
和最大的子数组为3,10,-4,7,2
因此输出为该子数组的和18。

2、C编程实现

针对该问题，采用了暴力穷举解法、分治算法、动态规划算法求解。

// 方法一：暴力解法 时间复杂度O(N^3)
int maxSubarray_org(int a[], int size)
{
    int iMaxSum = INT_MIN;
    int sum = 0;
    int i = 0, j = 0, k = 0;

    for (i = 0; i < size; i++)
    {
        for (j = i; j < size; j++)
        {
            sum = 0;
            for (k = i; k <= j; k++)
            {
                sum += a[k];
            }
            if (sum > iMaxSum)
                iMaxSum = sum;
        }
    }
    return iMaxSum;
}

// 方法一：暴力解法 优化版本 时间复杂度O(N^2)
int maxSubarray_org_opt(int a[], int size)
{
    int iMaxSum = INT_MIN;
    int sum = 0;
    int i = 0, j = 0, k = 0;

    for (i = 0; i < size; i++) // 从第i个位置开始寻找连续数据的最大值
    {
        sum = 0;
        for (j = i; j <= size; j++)
        {        
            sum += a[j];
            if (sum > iMaxSum)
                iMaxSum = sum;
        }
    }
    return iMaxSum;
}
// 方法二：采用分治的思想 时间复杂度 O(2*N)
int maxSubarray(int a[], int size)
{
    int iMaxSum = 0;
    int iLocalSum = 0;
    int i = 0;

    for(i = 0; i < size; i++)
    {
        iLocalSum += a[i];
        if(iLocalSum < 0)
        {
            iLocalSum = 0;  // 局部和出现小于0的情况，则设置为0
        }
        if(iLocalSum > iMaxSum)
        {
            iMaxSum = iLocalSum; // 更新局部最大和
        }
    }

    if(iMaxSum == 0)    // 子数组最大和出现负数情况下，取数组中的最大值。
    {
        iMaxSum = a[0];

        for(i = 1; i < size; i++)
        {
            if(iMaxSum < a[i])
                iMaxSum = a[i];
        }
    }

    return iMaxSum;
}

int max(int x, int y)
{
    return (x>y) ? x : y;
}
// 方法三：动态规划  时间复杂度O(N) 空间复杂度O(2*N)
int maxSubarray_DP(int a[], int size)
{
    int Start[50];
    int All[50];
    int i = 0;

    Start[size-1] = a[size-1];
    All[size-1] = a[size-1];

    for (i = size -2; i >= 0; i--)
    {
        Start[i] = max(a[i], a[i]+Start[i+1]);
        All[i] = max(Start[i], All[i+1]);
    }
    return All[0];
}

// 方法四： 动态规划 优化版本 时间复杂度 O(N) 空间复杂度O(1)
int maxSubarray_DP_opt(int a[], int size)
{
    int nStart = 0;
    int nAll = 0;
    int i = 0;
    nStart = a[size-1];
    nAll = a[size-1];

    for(i = size-2; i >=0; i--)
    {
        nStart = max(a[i], nStart + a[i]);
        nAll = max(nStart, nAll);
    }
    return nAll;
}

// 方法四：动态规划 另一种简便写法，这种写法体现了数学之美和编程之美！
int maxSubarray_DP_opt_v2(int a[], int size)
{
    int nStart = 0;
    int nAll = 0;
    int i = 0;
    nStart = a[size-1];
    nAll = a[size-1];

    for(i = size-2; i >=0; i--)
    {
        if (nStart < 0)
        {
            nStart = 0;
        }
        nStart += a[i];
        if (nStart > nAll)
        {
            nAll = nStart;
        }
    }
    return nAll;
}


//test demo
int main(int argc, char *argv[])
{
#if 0
    int array[8] = {1,-2,3,10,-4,7,2,-5};
    //int array[8] = {-2, 5, 3, -6, 4, -8, 6};
#else
    int array[8] = {-1,-2,-3,-10,-4,-7,-2,-5};
#endif

    int max_sum = 0;

    max_sum = maxSubarray_DP_opt_v2(array, 8);
    printf("max_sum_subarray: %d    \n", max_sum);
    return 0;
}

THE END!

---

本博文只能阅读，谢绝转载，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2963033731@qq.com