【动态规划】NK刷题记之DP8乘积为正数的最长连续子数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划】NK刷题记之DP8乘积为正数的最长连续子数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

1. 题目

老规矩，牛客网的一道中等难度的题目，我们先给出链接，大家可以去做一下这道题点击此处跳转

给定一个长度为 n的整数数组，请你找出其中最长的乘积为正数的子数组长度。
子数组的定义是原数组中一定长度的连续数字组成的数组。
$1 <= n<= 10^5$ ,数组元素 $\vert val\vert <=10^9$

2. 题解

1. 确定问题状态,提炼最后一步

先考虑简单的情况，假设从我遍历到当前位置不存在0这个特殊元素
现在我想求出以当前位置的元素a[i]为尾项乘积为正数的最大子数组长度该如何求呢？由于上一道题的经验，我们可以知道存在负负得正的情况，变量应该定义两个

定义positive这个变量表示以当前位置的元素a[i]为尾项乘积为正数的最长子数组长度
定义negative这个变量表示当前位置的元素a[i]为尾项乘积为负数的最长子数组长度

定义好了变量，我们只需要做3件事
1.确定a[i]的正负，负数的特殊性影响着整体的符号
2.知道positive和negative之前的状态
3.根据 $a [i]$ 的符号对这两个变量的值进行更新
第3件事做好了，循环可以解决前两件事，所以关键就在于如何更新这两个变量的值

2. 更新变量的值

当 $a [i] > 0 时$ ，positive++,negative视情况变化

$n e g a t i v e > 0$ ，说明此时存在负的以 $a [i]$ 为尾项的子数组乘积，再乘一个正数还是负数，所以negative++

特殊情况： $n e g a t i v e = 0$ ，说明此时以 $a [i]$ 为尾项的子数组乘积不存在负的，再乘一个正数也不会为负数，所以negative = 0

当 $a [i] < 0 时$ ，negative情况唯一，positive存在特殊情况

一般情况，negative和positive相互交换并加1

为什么是这样呢？为什么要negative和positive相互交换并加1呢？
这是因为只有负数会导致乘积符号的改变，所以负数很特殊，如果上一次我的以a[i-1]为尾项乘积为负数的最长子数组长度为a，上一次以a[i-1]为尾项乘积为正数的最长子数组长度为b，这一次再次乘一个负数，那么以a[i]为尾项的乘积为正数的最长子数组长度是不是就是a+1,而以a[i]为尾项乘积为负数的最长子数组长度不就是b+1吗？

特殊情况，当 $n e g a t i v e = 0$ ,即第一次遇见负数时，以a[i]为尾项的子数组乘积不存在正数，所以 $p os i t i v e = 0$

当 $a [i] = 0$ 时，negative和positive的值都要赋值为 $0$ ，因为此时当前位置以a[i]为尾项连续子数组的乘积均为 $0$

3.子问题转化

0的出现就像是把我的数组分成了一个个相互独立的小段，因为一旦出现了0，我的两个变量都要变成0，之前的数据和我的后面小段没有任何关联了，这不就是一个个子问题吗？虽然元素不同，但每一步要做的事都是相同的，即根据现有的信息更新两个变量的值

之后创建一个ret变量维护一个正数乘积子数组的最大值就可

3. 源码

#include<stdio.h>
#include<stdlib.h>
int Max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int* a = (int*)malloc(n * sizeof(int));
    int positive = 0;
    int negative = 0;
    int ret = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > 0) {
            positive++;
            negative = (negative == 0) ? 0 : negative+1;
        } 
        else if (a[i] < 0) 
        {       
                int temp = negative;
                negative = positive+1;
               if(temp)
                 positive = temp+1;
                 else positive = 0;
        }
        else {
            positive = 0;
            negative = 0;
        }
        ret = Max(ret, positive);
    }
    printf("%d", ret);
}

【动态规划】NK刷题记之DP8乘积为正数的最长连续子数组

4.总结

“人生不就是去解决一个个子问题吗，只有把每一步都走好，才会得到我们最终想要的那个标准答案，但即使我们有那么几步没有走好，或者走错了，那又何妨呢？因为我们的最终答案是在所有结果里面取一个最好的答案，总会有一些结果不尽如人意，但有时候那些我们在意的想得到的结果，就像我们这道题分别求出的很多positive,最终我们只取了那个最大的，那些小的部分，即使我们没求出来，在人生这样庞大而复杂的考卷中，很多问题都是独立的，你又怎么能保证我们没有得到的那个又恰恰是最重要的那个呢？很喜欢苏轼的一句诗歌，竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生，所以希望不管我们今后无论遇见什么困难，都能把它当成人生中一个很小很小的问题去看待，不可妄自菲薄，丧失了前行的勇气，最后送大家一句话，与诸君共勉，前路漫漫亦灿灿,往事堪堪亦澜澜”！！！
【动态规划】NK刷题记之DP8乘积为正数的最长连续子数组文章来源地址https://www.toymoban.com/news/detail-492284.html