当前位置：首页 > news >正文

题解：力扣1567 - 返回乘积为正数的最长子数组

news 来源：原创 2024/9/20 19:52:36

问题描述

给定一个整数数组 nums，找出乘积为正数的最长子数组的长度。这里的子数组定义为连续元素的序列，乘积为正数指子数组中正数的个数必须大于负数的个数。

解题思路

为了解决这个问题，我们可以使用两个数组 f 和 g 分别表示以当前位置结尾的乘积为正数和乘积为负数的最长子数组长度。

状态表示：
- f[i]：以 i 位置结尾的乘积为正数的最长子数组长度。
- g[i]：以 i 位置结尾的乘积为负数的最长子数组长度。
状态转移方程：
- 当 nums[i] > 0 时：
  - f[i] = f[i-1] + 1
  - g[i] = g[i-1] != 0 ? g[i-1] + 1 : 0
- 当 nums[i] < 0 时：
  - f[i] = g[i-1] != 0 ? g[i-1] + 1 : 0
  - g[i] = f[i-1] + 1
- 当 nums[i] == 0 时：
  - 直接令 f[i] = g[i] = 0，因为乘积为零无法满足乘积为正数的条件。
初始化：
- 初始时，f[0] = g[0] = 0，表示在开始处没有乘积为正数或负数的子数组。
填表顺序：
- 从数组的第一个元素开始遍历到最后一个元素，依次更新 f[i] 和 g[i] 的值。
返回值：
- 最终结果为 f 数组中的最大值，即乘积为正数的最长子数组长度。

Java 代码实现

package study1.day12;
/*
* 力扣1567 返回乘积为正数的最长子数组
*           思路分析:
*               1.状态表示 f[i]以i位置结尾的积为正数最长的子数组
*                         g[i]以i位置结尾的积为负数最长的子数组
*               2.状态转移方程 f[i] = f[i - 1] + 1  nums[i]为正数 g[i - 1] + 1 nums[i]为负数(== 0 不可)
*                            g[i] = f[i - 1] + 1  nums[i]为负数 f[i - 1] + 1 nums[i]为正数(== 0 不可)
*               3.初始化 任何数 + 0 = 任何数 所以f[0] = g[0] = 0 即可
*               4.填表顺序 正常
*               5.返回值 f[i]中的最大值
*
* */
public class test6 {public int getMaxLen(int[] nums) {//本题先讲我的错误思路:  我没有分析 == 0不可就导致全盘皆输 因为(全为正遇见负f[i]归 0)//我的思维漏洞就是我的想法就是错的，我认为f[i]是保存前面的最大长度(不是以i结尾是全部)这就是我的错误点//记住你：一定要紧跟状态转移方程int n = nums.length;//1.创建f g数组记录历史记录int[] f = new int[n + 1];int[] g = new int[n + 1];//2.初始化f[0] = g[0] = 0;//默认值可以填可以不填int ret = 0;//3.填表for (int i = 1; i <= n; i++) {//这里 == 0的情况没有考虑直接让值 = 0即可int x = f[i - 1] + 1;int y = g[i - 1] + 1;if (nums[i - 1] > 0){f[i] = x;g[i] = g[i - 1] != 0 ? y : 0;} else if (nums[i - 1] < 0) {f[i] = g[i - 1] != 0 ? y : 0;g[i] = x;}ret = Math.max(ret,f[i]);}return ret;}
}