【动态规划】NK刷题之DP7 连续子数组的最大乘积网站首页 其他

【动态规划】NK刷题之DP7 连续子数组的最大乘积

小镇敲码人 2024-09-16 12:01:04

简介【动态规划】NK刷题之DP7 连续子数组的最大乘积

【动态规划】NK刷题之DP7 连续子数组的最大乘积

1.题目
2.题解
3.代码部分
4.总结与感悟

❤️博客主页：小镇敲码人
? 欢迎关注：?点赞 ??留言 ?收藏
?在一切变好之前，我们总要经历一些不开心的日子，这段日子也许很长，也许只是一觉醒来。有时候，选择快乐，更需要勇气。
? 如果你也迷失在了路上，对人生充满了迷惘，不要害怕，冷静下来，慢慢的自救，不断求知，让自己变得更加优秀吧！！!

1.题目

牛客网上面的题我们先给出链接，有需要的朋友可以点击下面链接去做一下点击此处跳转

输入一个长度为 n 的整型数组 nums，数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。

子数组是连续的，且最小长度为 1 ，最大长度为 n
长度为 1 的子数组，乘积视为其本身，比如 [4] 的乘积为 4
该题的数据保证最大的乘积不会超过 int的范围，即不
超过2³²-1

2.题解

1.首先我们要知道这道题与【动态规划】NK刷题记之DP6 连续子数组最大和（C语言实现）的区别在于这道题多了负负得正的情况¹，因此简单的只维护一个最大值已经达不到我们的要求了，那么我们就需要维护两个值，一个维护当前连续子数组的最大值，一个维护当前连续子数组的最小值。

问题来了，该如何维护这两个最大值和最小值呢？
首先我们要创建两个动态数组dp1[i]与dp2[i]，用来保存当前位置连续子数组的最大值和最小值，可以知道 $d p 1 [i] >= d p 2 [i]$ 1️⃣
其次我们思考哪些值可以更新dp1呢,我们可以考虑所有可能的情况
1. $a [i] > 0, d p 1 [i - 1] > 0$ ，由1️⃣不能知道dp2[i-1]的正负，此时 $d p 1 [i] = a [i] * d p 1 [i - 1]$ ,需要讨论dp2[i-1]的情况，才可以确定dp2[i-1]的表达式
1.1 $d p 2 [i - 1] > 0, d p 2 [i] = a [i]$
1.2 $d p 2 [i - 1] <= 0, d p 2 [i] = d p 2 [i - 1] * a [i]$
1. $a [i] > 0, d p 1 [i - 1] <= 0$ ,由1️⃣可以知道 $d p 2 [i - 1] <= 0$ ,此时 $d p 1 [i] = a [i] ， d p 2 [i - 1] = d p 2 [i - 1] * a [i]$
2. $a [i] < 0, d p 1 [i - 1] > 0$ , 由1️⃣不能知道dp2[i-1]的正负,此时 $d p 2 [i - 1] = d p 1 [i - 1] * a [i]$ ,要讨论dp2[i-1]的情况，才可以确定dp1[i-1]的表达式
3.1 $d p 2 [i - 1] > 0, d p 1 [i] = a [i]$
3.2 $d p 2 [i - 1] < 0, d p 1 [i] = d p 2 [i - 1] * a [i]$
1. $a [i] < 0, d p 1 [i - 1] <= 0, 由 : o n e : 可以知道 d p 2 [i - 1] <= 0, 此时 d p 1 [i] = d p 2 [i - 1] * a [i], d p 2 [i] = a [i]$
  5. $a [i] = 0, d p 1 [i] 与 d p 2 [i] 都为 0$ ，代入哪个表达式均可
通过上述推理我们知道了dp1[i]和dp2[i]是如何更新的，我们可以把上述推理通过编程语言来表示出来，if语句可以实现，但是没必要，因为可以观察到，更新dp1[i],dp2[i]的表达式只有那么3个，即 $d p 1 [i - 1] * a [i]$ , $d p 2 [i - 1] * a [i]$ , $a [i]$ ,所以我们在这三者里面取一个最大值和最小值就不需要繁琐的if语句判断了
状态转移方程：
$d p 1 [i] = M a x (d p 1 [i - 1] * a [i], d p 2 [i - 1] * a [i], a [i])$
$d p 2 [1] = M in (d p 1 [i - 1] * a [i], d p 2 [i - 1] * a [i], a [i])$
我们创建临时变量ret来维护连续子数组的最大值，ret = max(ret,dp1[i])
4. 有了递推式，就可以去循环求解了，进行代码实现了。

3.代码部分

法一：动态规划

3.1.1 创建变量n，并读入数据

 int n = 0;
 scanf("%d", &n);

3.1.2 创建动态数组，并初始化

    int* a = (int*)malloc(n * sizeof(int));//创建变量a，来读入原始数组
    /*dp1用来表示遍历到a[i]时连续子数组乘积的最大值，
    而dp2[i]用来表示遍历到a[i]时连续子数组乘积的最小值*/
    int* dp1 = (int*)malloc(n * sizeof(int));
    int* dp2 = (int*)malloc(n * sizeof(int));
    memset(a, 0, n * sizeof(int));
    memset(dp1, 0, n * sizeof(int));
    memset(dp2, 0, n * sizeof(int));

3.1.3 对动态数组断言

    assert(dp1 && dp2 && a);

3.1.4 读入原整形数组的数据

    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

3.1.5 创建变量ret，并赋初值

    dp1[0] = a[0];
    dp1[0] = a[0];
    int ret = a[0];//创建ret变量，初始化ret，这里就考虑了n==1的情况

3.1.6 循环实现关键递推式部分

for(int i = 1; i < n; i++) {
	dp1[i] = Max(dp1[i - 1] * a[i], dp2[i - 1] * a[i], a[i]);
	dp2[i] = Min(dp1[i - 1] * a[i], dp2[i - 1] * a[i], a[i]);
	ret = Max1(ret, dp1[i]);//维护所有连续子数组乘积中的最大值
}

3.1.7 C语言完整代码

注意这里纠正之前博客的一个错误，动态内存分配和释放必须对应，即有分配就必须有释放，不释放内存会产生“内存泄漏”，后果是随着程序运行多次，可以使用的内存空间越来越少；另一方面，再次释放已经释放的内存空间，会导致程序出现崩溃性错误

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
int Max1(int a, int b) {
    if (a > b)
        return a;
    return b;
}
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
int Max(int a, int b, int c) {
    if (b > a)
        swap(&a, &b);
    if (c > a)
        swap(&c, &a);
    return a;
}
int Min(int a, int b, int c) {
    if (a > c)
        swap(&c, &a);
    if (a > b)
        swap(&a, &b);
    return a;
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int* a = (int*)malloc(n * sizeof(int));//创建变量a，来读入原始数组
    /*dp1用来表示遍历到a[i]时连续子数组乘积的最大值，
    而dp2[i]用来表示遍历到a[i]时连续子数组乘积的最小值*/
    int* dp1 = (int*)malloc(n * sizeof(int));
    int* dp2 = (int*)malloc(n * sizeof(int));
    /*
    进行动态数组的初始化和断言，防止出现空指针的情况
  */
    memset(a, 0, n * sizeof(int));
    memset(dp1, 0, n * sizeof(int));
    memset(dp2, 0, n * sizeof(int));
    assert(dp1 && dp2 && a);
    /*读入数据*/
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    dp1[0] = a[0];
    dp1[0] = a[0];
    int ret = a[0];//创建ret变量，初始化ret，这里就考虑了n==1的情况
    for (int i = 1; i < n; i++) {
        dp1[i] = Max(dp1[i - 1] * a[i], dp2[i - 1] * a[i], a[i]);
        dp2[i] = Min(dp1[i - 1] * a[i], dp2[i - 1] * a[i], a[i]);
        ret = Max1(ret, dp1[i]);//维护所有连续子数组乘积中的最大值
    }
    free(dp1 && dp2 && a);//释放分配的内存
    printf("%d", ret);打印连续数组乘积的最大值
}

3.1.7 优化代码

优化就是观察到每一次遍历都只需要用到dp1[i],dp1[i-1],dp2[i],dp2[i-1],把两个大的动态数组用4个临时变量来表示，节省了空间

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
int Max1(int a, int b) {
    if (a > b)
        return a;
    return b;
}
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}
int Max(int a, int b, int c) {
    if (b > a)
        swap(&a, &b);
    if (c > a)
        swap(&c, &a);
    return a;
}
int Min(int a, int b, int c) {
    if (a > c)
        swap(&c, &a);
    if (a > b)
        swap(&a, &b);
    return a;
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int* a = (int*)malloc(n * sizeof(int));
    memset(a, 0, n * sizeof(int));
    assert(a);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    int MAX = a[0];
    int MIN = a[0];
    int ret = a[0];
    for (int i = 1; i < n; i++) {
        int MAXbefore = 0;
        int MINbefore = 0;
        MAXbefore = MAX;
        MINbefore = MIN;
        MAX = Max(MAXbefore* a[i], MINbefore * a[i], a[i]);
        MIN = Min(MAXbefore* a[i], MINbefore * a[i], a[i]);
        ret = Max1(ret, MAX);
    }
    free(a);
    printf("%d", ret);
}

3.2 法二:分治

3.2.1 基本思路

将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
先考虑一种最简单的情况，没有0，该如何求连续子数组的最大值，很简单你可能会这样去做
1. 创建一个临时变量sum，把循环把数组的乘积存入sum中
1. $s u m > 0$ ，他就是这个连续子数组数组乘积的最大值
2. $s u m < 0$ ,这个时候如何得到连续子数组的乘积最大值呢？很简单我们把 $s u m$ 从前往后除以 $a [i]$ 直到得到一个正数停止，或者是把 $s u m$ 从后往前除直到得到一个正数停止，这样我们再从这两个数中取一个最大值就为连续子数组的乘积最大值了
1. 那有0的时候该怎么办呢，也很简单，遍历到0停止，然后做一样的事情就行了
  当然这只是一个大体的思路还有很多细节需要去处理
- 注意有0的情况相当于把一个大的数组分成了很多段小的连续子数组想要求这些连续子数组的乘积最大值，方法是一样的
3.2.2 创建临时变量n,并读入数据
```
  int n = 0;
  scanf("%d", &n);//创建变量n，并读入数据
```

  #### 创建动态数组a和dp，并进行断言
  ```c
  /*创建动态数组a和dp，一个用来读入原始数组的数据，
    一个用来储存不同段连续子数组乘积的最大值*/
    int* a = (int*)malloc(n * sizeof(int));
    int* dp = (int*)malloc(n * sizeof(int));
     assert(dp && a);//断言，防止出现空指针的情况

3.2.3 把数据读入动态数组a中

 for(int i = 0; i < n; i++) //读入原始数组的数据
      scanf("%d", &a[i]);

3.2.4 创建临时变量ret，sum，left，right，v，并赋初值

  int v = 0;//创建临时变量，用来表示动态数组dp的下标
  int left = 0;//表示一段连续子数组的最左边下标
  int right = 0;//表示一段连续子数组的最右边下标
  int sum = a[0];//表示遍历到当前位置的连续子数组的乘积，注意a[i]如果等于0，sum就不会乘上这个a[i]

3.2.5 循环实现求所有可能的连续子数组乘积最大值，并用ret变量维护一个最大的

/*循环实现具体的算法*/
 for (int i = 1; i < n; i++) {
     if (a[i] == 0 || i == n-1) {
        //某一段可能没有0，
         //但是已经遍历到数组的最后了，我们需要考虑这种情况
          if(a[i]!= 0)
             sum *= a[i];
         right = i;
         //更新right的值，
         //是因为存在没有0的情况，如果不更新为i的话可能
         //会导致最后一个数据丢失而出bug，不能因小失大
         if (sum > 0 || left == right)   
          dp[v++] = sum;
         //left == right的情况是前面有0，
        //然后最后只剩下最后一个数据的情况，
        //很明显这一个数据的最大乘积就是它本身
         else if(right - left == 1 && a[i] == 0)
             dp[v++] = 0;
           //这个情况就是sum < 0
           //且这一小段只有2个数据的情况，一个负数和0，很明显乘积最大值应该是0
         else
             max_product(dp, a, left, right, sum, &v);
             //传入相应的值，计算这一小段的连续子数组乘积最大值
         left = right + 1;//left更新下一段子数组从不为0的开始
         sum = 1;//重置sum的值
         ret  = Max(ret, dp[v - 1]);//维护所有段连续子数组乘积的最大值
     }
     else
     {
         sum *= a[i];//没有遇见特殊情况正常数组相乘并存入sum中
     }
 }

3.2.6 创建函数max_product求某一段有负数连续数组的乘积最大值

void max_product(int* answer, int* a, int left, int right, int sum) {
 int sum1 = sum;
 for (int i = left; i <= right; i++) {
     if (a[i] == 0)
         continue;
     sum1 /= a[i];
     if (sum1 > 0)
         break;
 }
 for (int i = right; i >= left; i--) {
     if (a[i] == 0)
         continue;
     sum /= a[i];
     if (sum > 0)
         break;
 }
 *answer= Max(sum, sum1);
}

3.2.8 释放动态数组内存，并打印最大值

/*释放分配的
 动态数组的内存*/
 free(a);
 free(dp);
 printf("%d", ret);//打印不同段的连续子数组乘积的最大值

3.2.7 C语言完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
int Max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
void max_product(int* dp, int* a, int left, int right, int sum, int* v) {
    int sum1 = sum;
    for (int i = left; i <= right; i++) {
        if (a[i] == 0)
            continue;
        sum1 /= a[i];
        if (sum1 > 0)
            break;
    }
    for (int i = right; i >= left; i--) {
        if (a[i] == 0)
            continue;
        sum /= a[i];
        if (sum > 0)
            break;
    }
    dp[(*v)++] = Max(sum, sum1);
}
int main() {
    int n = 0;
    scanf("%d", &n);//创建变量n，并读入数据
    /*创建动态数组a和dp，一个用来读入原始数组的数据，
    一个用来储存不同段连续子数组乘积的最大值*/
    int* a = (int*)malloc(n * sizeof(int));
    int* dp = (int*)malloc(n * sizeof(int));
     assert(dp && a);//断言，防止出现空指针的情况
     for (int i = 0; i < n; i++) //读入原始数组的数据
        scanf("%d", &a[i]);
    int v = 0;//创建临时变量，用来表示动态数组dp的下标
    int left = 0;//表示一段连续子数组的最左边下标
    int right = 0;//表示一段连续子数组的最右边下标
    int sum = a[0];//表示遍历到当前位置的连续数组的乘积，注意a[i]如果等于0，sum就不会乘上这个a[i]
    int ret = a[0];//创建一个临时变量来维
                     //护不同段连续子数组乘积最大值
    /*循环实现具体的算法*/
    for (int i = 1; i < n; i++) {
        if (a[i] == 0 || i == n-1) {
           //某一段可能没有0，
            //但是已经遍历到数组的最后了，我们需要考虑这种情况
             if(a[i]!= 0)
                sum *= a[i];
            right = i;
            //更新right的值，
            //是因为存在没有0的情况，如果不更新为i的话可能
            //会导致最后一个数据丢失而出bug，不能因小失大
            if (sum > 0 || left == right)   
             dp[v++] = sum;
            //left == right的情况是前面有0，
           //然后最后只剩下最后一个数据的情况，
           //很明显这一个数据的最大乘积就是它本身
            else if(right - left == 1 && a[i] == 0)
                dp[v++] = 0;
              //这个情况就是sum < 0
              //且这一小段只有2个数据的情况，一个负数和0，很明显乘积最大值应该是0
            else
                max_product(dp, a, left, right, sum, &v);
                //传入相应的值，计算这一小段的连续子数组乘积最大值
            left = right + 1;//left更新下一段子数组从不为0的开始
            sum = 1;//重置sum的值
            ret  = Max(ret, dp[v - 1]);//维护所有段连续子数组乘积的最大值
        }
        else
        {
            sum *= a[i];//没有遇见特殊情况正常数组相乘并存入sum中
        }
    }
    /*释放分配的
    动态数组的内存*/
    free(a);
    free(dp);
    printf("%d", ret);//打印不同段的连续子数组乘积的最大值
    return 0;
}

3.2.8 优化

同理这里的优化也是在空间上进行优化，每一次只用到了当前的dp[i],我们直接用临时变量来代替

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
int Max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
void max_product(int* answer, int* a, int left, int right, int sum) {
    int sum1 = sum;
    for (int i = left; i <= right; i++) {
        if (a[i] == 0)
            continue;
        sum1 /= a[i];
        if (sum1 > 0)
            break;
    }
    for (int i = right; i >= left; i--) {
        if (a[i] == 0)
            continue;
        sum /= a[i];
        if (sum > 0)
            break;
    }
    *answer= Max(sum, sum1);
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int* a = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) 
        scanf("%d", &a[i]);
    int left = 0;
    int right = 0;
    int sum = a[0];
    int ret = a[0];
    int  answer = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] == 0 || i == n-1) {
            if(a[i]!= 0)
              sum *= a[i];
            right = i;
            if (sum > 0 || left == right)
                answer = sum;
            else if(right - left == 1 && a[i] == 0)
                answer = 0;
            else
                max_product(&answer, a, left, right, sum);
            left = right + 1;
            sum = 1;
            ret  = Max(ret, answer);
        }
        else
        {
            sum *= a[i];
        }
    }
    printf("%d", ret);
    return 0;
}

4.总结与感悟

这个题虽然是中等难度的题目，但对我的帮助还是挺大，让我对分治和动态规划这两种算法又有了更深的理解，分治法和动态规划这两种方法都可以AC这道题，看自己更擅长哪一种吧，我更喜欢动态规划的简洁，因为分治要注意的细节还是挺多的，容易写出bug，最后关于这篇博客有什么问题和不足，欢迎大家在评论区告诉我哦??.