C语言刷题之动态规划入门(三)_第一行一个整数n,表示初始数组的大小c语言

1.前言

        上期我们学习了动态规划三道入门例题，对动态规划有了更进一步的了解。传送门：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