C语言刷题之动态规划入门(三)

Dear 丶 2024-03-30 08:49 70阅读 0赞

### 1.前言 ###

上期我们学习了动态规划三道入门例题，对动态规划有了更进一步的了解。传送门：[C语言刷题之动态规划入门(二)][C]。那么本期就是动态规划入门篇的最后一篇，迎接突破挑战吧！

> 这期的几道题目分别是：连续子数组最大和，连续子数组最大乘积以及乘积为正数的最长连续子数组

### 2.连续子数组最大和 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 给定一n的数组，数组中的数为整数。
> 
> 请你选择一个**非空连续**子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。
> 
> #### 输入描述： ####
> 
> 第一行为一个正整数n，代表数组的长度。 1≤n≤200000
> 
> 第二行为n个整数 ai，用空格隔开，代表数组中的每一个数。
> 
> #### 输出描述： ####
> 
> 连续子数组的最大之和。

--------------------

#### 2.初步分析 ####

本体容易做错的地方在于题目要求的最大子数组要求是连续的，如果我们简单的利用动态规划进行遍历赋值，然后输出第n项，就会落入陷阱。在本题中，这个最大连续子数组可能是中间的任意几个连续元素，也可能是dp\[i\]，甚至可能是数组的其中一个元素，所以应该对dp数组所有元素进行比较。值得注意的是，在解题的时候要细心考虑，避免所求的数组断开。

> **我的思路是**：将其分为两步，第一步是利用动态规划建立一个dp\[n\]，通过转移公式dp\[i\]=max(dp\[i-1\]+arr\[i\]，arr\[i\])可以找出包含arr\[i\]的最大连续子数组，第二步是创建一个变量Max存储过往的连续最大子数组，并通过Max=max(dp\[i\], Max)对最大值进行更新。通过第一步我们可以求出包含某一项的最大连续子数组，而题目所求的非空连续子数组一定是包含在这些值里面，所以再通过第二步求出最大值即可。

--------------------

#### 3.代码实现 ####

#include <stdio.h>
    #include <stdlib.h>
    int max(int x,int y)
    {
        return x>y?x:y;
    }
    int main()
    {
    	int n = 0;
    	int Max = 0;             //存储实际的最大值，记录过往的连续数组最大值
    	scanf("%d", &n);
    	int* arr = (int*)malloc(n * sizeof(int));
    	int* dp = (int*)malloc(n * sizeof(int));    //建立dp数组，代表含dp[i]的最大连续数组
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &arr[i]);
    	}
    	dp[0] = arr[0];           //赋初值
    	Max = arr[0];              //当n=1时实际最大连续数组和为arr[0]
    	for (int i = 1; i < n; i++)
    	{
    		dp[i] = max(dp[i - 1] + arr[i], arr[i]);       //求出含dp[i]的最大连续数组，题目所求数 
                                                           //组和一定在这些元素之中
    
    		Max = max(dp[i], Max);                         //和Max比较，更新Max，不断更新求出dp数 
                                                           //组元素最大值,即为题目所求 
    	}
    	printf("%d", Max);
    	free(arr);
    	free(dp);
    	return 0;
    }

### 3.连续子数组的最大乘积 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 输入一个长度为 n 的整型数组 nums，数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。
> 
> 1.子数组是连续的，且最小长度为 1 ，最大长度为 n
> 
> 2.长度为 1 的子数组，乘积视为其本身，比如 \[4\] 的乘积为 4
> 
> 3.该题的数据保证最大的乘积不会超过 int 的范围
> 
> 数据范围:
> 
> 第一行为一个正整数n，代表数组的长度。 1≤n≤200000
> 
> 第二行为n个整数 ai，用空格隔开，代表数组中的每一个数。
> 
> #### 输入描述： ####
> 
> 第一行输入一个正整数 n ，表示数组的长度
> 
> 第二行输入 n 个整数，表示数组中的值。
> 
> #### 输出描述： ####
> 
> 输出子数组的乘积的最大值

--------------------

#### 2.初步分析 ####

这题是上题的改编题，不同于求最大和的情况，当我们遇到负数时，dp数组的状态转移方程需要考虑到负负得正的情况，不能简单的将最小项舍去。

> **我的思路是**：因为一个最小负数再乘以一个负数就会变成最大正数，所以在上一题的基础上，增加一个dp\_min数组来存储包含arr\[i\]的最小连续子数组，在状态转移方程比较大小时一同与dp\_min\[i\]与当前项的乘积进行比较。这样，就有两个状态转移方程，分别为：
> 
> dp\_max\[i\]=max(max(dp\_max\[i-1\]\*arr\[i\]，arr\[i\]),dp\_min\[i-1\]\*arr\[i\])\------------------dp\_max数组
> 
> dp\_min\[i\]=minin(min(dp\_min\[i-1\]\*arr\[i\]，arr\[i\]),dp\_max\[i-1\]\*arr\[i\])\------------------dp\_min数组
> 
> 最后找出dp\_max数组的最大值即为题目所求。

--------------------

#### 3.代码实现 ####

#include <stdio.h>
    #include <stdlib.h>
    int max(int x,int y)
    {
        return x>y?x:y;
    }
    int min(int x,int y)
    {
        return x<y?x:y;
    }
    int main()
    {
    	int n = 0;
    	int Max = 0;             //存储实际的最大值，记录过往的连续数组最大值
    	scanf("%d", &n);
    	int* arr = (int*)malloc(n * sizeof(int));
    	int* dp_max = (int*)malloc(n * sizeof(int));   //建立dp_max数组，代表含dp_max[i]的最大 
                                                       //连续子数组
        int* dp_min= (int*)malloc(n * sizeof(int));    //建立dp_min数组，代表含dp_max[i]的最小 
                                                       //连续子数组
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &arr[i]);
    	}
    	dp_max[0] = arr[0];           //赋初值
    	dp_min[0] = arr[0];
    	Max = arr[0];              //当n=1时实际最大连续数组和为arr[0]
    	for (int i = 1; i < n; i++)
    	{
            //通过状态转移方程求出包含arr[i]的最大和最小连续乘积子数组
    		dp_max[i] = max(max(dp_max[i - 1]*arr[i], arr[i]),dp_min[i - 1]*arr[i]);
            dp_min[i] = min(min(dp_min[i - 1]*arr[i], arr[i]),dp_max[i - 1]*arr[i]);
            //更新Max，因为题目所求一定为在dp_max数组的最大值
    		Max = max(dp_max[i], Max);
    	}
    	printf("%d", Max);
    	free(arr);
    	free(dp_max);
    	free(dp_min);
    	return 0;
    }

### 4.乘积为正数的最长连续子数组 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 给定一个长度为 n 的整数数组，请你找出其中最长的乘积为正数的子数组长度。
> 
> 子数组的定义是原数组中一定长度的连续数字组成的数组。
> 
> 数据范围：1≤n≤100000
> 
> #### 输入描述： ####
> 
> 第一行输入一个正整数 n ，表示数组长度。
> 
> 第二行输入 n 个整数，表示数组中的元素。
> 
> #### 输出描述： ####
> 
> 输出最长的乘积为正数的子数组长度

--------------------

#### 2.初步分析 ####

依旧是一个长度为n的数组，要求求出符合条件连续子数组。通过已有的数学知识，我们知道乘积为正数有两种情况，负值与负值相乘和正值与正值相乘。因此照葫芦画瓢，我们可以开辟两个数组，一个代表当前项最长正值，一个代表当前项最长负值。但我们通过前两题可以发现，数组中的每个元素我们仅用了一次，所以我们其实只需两个变量以便节省空间。然后通过状态转移方程进行求解。

> **我的思路是：**
> 
> 设置当前项最长正值positive和当前项最长负值negative，通过分析我们可以得到它们的状态转移方程为：
> 
> negative = 0，positive = 0;(清空)\----------------------------------------------arr\[i\]=0
> 
> positive=positive+1; negative=0 (计数)\--------------------------------------arr\[i\]>0且negative==0
> 
> positive=positive+1; negative=negative+1 (计数)\-------------------------arr\[i\]>0且negative!=0
> 
> positive=0; negative=positive+1(交换)\---------------------------------------arr\[i\]<0且negative==0
> 
> positive=negative+1; negative=positive+1(交换)\--------------------------arr\[i\]<0且negative!=0
> 
> 通过状态转移方程遍历数组中的所有项，然后和之前一样，创建一个变量len记录遍历过程中实际的最大长度，即可求出答案。

--------------------

#### 3.代码实现 ####

#include <stdio.h>
    #include <stdlib.h>
    int main()
    {
        int negative = 0, positive = 0, len = 0;     //存储包括当前项的最长负值数，最长正值数和 
                                                     //实际最大正值长度，
        int n = 0;
        scanf("%d", &n);
        int* arr = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
            if (arr[i] == 0)                        //遇见0，重新开始计数，任何数乘0都为0
            {
                negative = 0;
                positive = 0;
            }
            else if (arr[i] > 0)                    //遇见正值，则将最长正值数加1
            {
                positive++;
                if (negative != 0)                  //如果最长负值数不为0，则加1，因为为0代表还                                              
                {                                   //没有出现负值
                    negative++;
                }
            }
            else if (arr[i] < 0)                    //遇见负值，将最长正值数与最长负值数交换
            {
                int temp = negative;
                negative = positive + 1;            //最长正值数变为最长负值数
                if (temp != 0)                      //前面数组出现过负值
                {
                    positive = temp + 1;            //最长负值数变为最长正值数
                }
                else                                //前面没出现过负值，没有包含当前项最长正值， 
                {                                   //计数清零
                    positive = 0;
                }
            }
            len = len > positive ? len : positive;   //每次更新实际最长正值数
        }
        printf("%d", len);
        free(arr);
        return 0;
    }

--------------------

### 5.总结 ###

> 通过这三题我们不难发现，题目都是围绕连续最长子数组这一关键词展开。因此关于这类题型，我们可以总结出以下4点方法：
> 
> 1.建立一个包含当前项的最优解的dp数组或变量。
> 
> 2.找出当前项与数组上一项的关系，得出状态转移方程。
> 
> 3.根据状态转移方程进行遍历赋值。
> 
> 4.最后由于我们不知道答案包含数组哪一项，因此需要再创建一个变量在赋值时实时更新记 录题目所求的真正最优解。

--------------------

***以上，就是动态规划入门刷题(三)的全部内容。***

***制作不易，能否点个赞再走呢qwq***

[C]: http://t.csdn.cn/YkDfn