动态规划(DP)理解—C语言_c语言动态规划 简书

说明：本人是一个菜鸟，接触到动态规划，有点想法。所以分享一下，有不严谨的地方望大佬指正。

我将从力扣的一道题目来说明我对想法：

题目：

做题前的思考：要找和最大的连续子数组，那么我们就是要找到所有的子数组，然后比较他们的大小，但是如果是想先找含有1个大小的数组，再找含有2个大小的数组...的话，那就需要计算n*(n+1)/2个数组的大小，不仅多，而且实现起来也比较麻烦。

想法一：在之前的思考上，这时候再往下思索就可以想到一个方便实现的想法，该方法就是把包含第一个元素的1个大小数组，2个大小数组...9的大小数组进行计算比较，找到最大的数并存入新数组arr中，然后再对第二个元素进行相同操作，一直到最后一个元素。虽然他也需要计算n*(n+1)/2个数组，但是该想法容易实现。

代码如下：

int maxSubArray(int *nums, int numsSize)//nums是传入数组，numSize是数组大小
{
    int arr[numsSize];//新数组
    for (int i = 0; i < numsSize; i++)//9次循环，从-2，1，-3，4，-1，2，1，-5，4
    {
 
        int max = nums[i];//定义最大值
        for (int j = i; j < numsSize; j++)//每个数都有numsSize-i个组合
        { //该循环得到一组最大值
            int sum = 0;
            for (int a = i; a <= j; a++)
            {
                sum += nums[a];
            }
            if (max < sum)
            {
                max = sum;
            }
        }
 
        arr[i] = max;//得到numsSize-i个组合中的最大值
    }
 
    int m = arr[0];
    for (int p = 0; p < numsSize; p++)
    { //在新建数组中查找最大数
        if (arr[p] > m)
        {
            m = arr[p];
        }
    }
 
    return m;
}

力扣提交结果：

说明：该算法的时间复杂度为O(n^3)，对于他提示中的三个样例是能很快执行的，但是当测试数组的大小达到上万个元素，他的执行速度很慢。可以试试哟，他会给出一个超级大的测试数组

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/87214