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

2024-02-08 01:59

本文主要是介绍【动态规划】NK刷题记之DP8乘积为正数的最长连续子数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

  • 1. 题目
  • 2. 题解
    • 1. 确定问题状态,提炼最后一步
    • 2. 更新变量的值
    • 3.子问题转化
  • 3. 源码
  • 4.总结


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

1. 题目

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

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

2. 题解

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

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

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

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

2. 更新变量的值

  1. a [ i ] > 0 时 a[i] > 0时 a[i]>0positive++,negative视情况变化
  1. n e g a t i v e > 0 negative>0 negative>0,说明此时存在负的以 a [ i ] a[i] a[i]为尾项的子数组乘积,再乘一个正数还是负数,所以negative++
  2. 特殊情况: n e g a t i v e = 0 negative = 0 negative=0,说明此时以 a [ i ] a[i] a[i]为尾项的子数组乘积不存在负的,再乘一个正数也不会为负数,所以negative = 0
  1. a [ i ] < 0 时 a[i] < 0时 a[i]<0negative情况唯一,positive存在特殊情况
  1. 一般情况,negativepositive相互交换并加1

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

  1. 特殊情况,当 n e g a t i v e = 0 negative = 0 negative=0,即第一次遇见负数时,以a[i]为尾项的子数组乘积不存在正数,所以 p o s i t i v e = 0 positive=0 positive=0
  1. a [ i ] = 0 a[i]=0 a[i]=0时,negativepositive的值都要赋值为 0 0 0,因为此时当前位置以a[i]为尾项连续子数组的乘积均为 0 0 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);
}

在这里插入图片描述

4.总结

人生不就是去解决一个个子问题吗,只有把每一步都走好,才会得到我们最终想要的那个标准答案,但即使我们有那么几步没有走好,或者走错了,那又何妨呢?因为我们的最终答案是在所有结果里面取一个最好的答案,总会有一些结果不尽如人意,但有时候那些我们在意的想得到的结果,就像我们这道题分别求出的很多positive,最终我们只取了那个最大的,那些小的部分,即使我们没求出来,在人生这样庞大而复杂的考卷中,很多问题都是独立的,你又怎么能保证我们没有得到的那个又恰恰是最重要的那个呢?很喜欢苏轼的一句诗歌,竹杖芒鞋轻胜马,谁怕?一蓑烟雨任平生,所以希望不管我们今后无论遇见什么困难,都能把它当成人生中一个很小很小的问题去看待,不可妄自菲薄,丧失了前行的勇气,最后送大家一句话,与诸君共勉,前路漫漫亦灿灿,往事堪堪亦澜澜”!!!

这篇关于【动态规划】NK刷题记之DP8乘积为正数的最长连续子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/689597

相关文章

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.