Ricky.L的随笔
0%

LeetCode.1567.乘积为正数的最长子数组长度（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.1567.乘积为正数的最长子数组长度（中等）

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。

题解

最优化问题考虑用动态规划，先从某个状态倒推拆解问题。

定义状态

设positive[i]是以nums[i]结尾的子数组中，乘积为正数的最长连续子数组的长度。

如何保证乘积为正数？

正数 * 正数
负数 * 负数

以nums[i]结尾的子数组有哪些组合情况？

按照nums[i]要不要拿去做乘法，分为：

  1. nums[i]单独为一个子数组
  2. nums[i]跟前面的子数组连接

实际去求positive[i]，肯定是尽量与前面的子数组的乘积去相乘，这样会得到尽可能大的结果长度。
如果nums[i]没法跟前面的子数组乘积相乘，再单独把nums[i]作为子数组。

如何保证以nums[i]结尾的子数组乘积为正数？

  1. nums[i]单独为一个子数组时，nums[i]要为正数
  2. nums[i]跟前面的子数组连接时
    1. nums[i]为正，前面子数组乘积为正
    2. nums[i]为负，前面子数组乘积为负

这里还要记录前面子数组乘积为负数的最长长度，可以定义negative[i]是以nums[i]结尾的子数组中乘积为负数的最长连续子数组的长度。

考虑边界情况

  1. 在nums[i]要跟前面的子数组连接时，如果：
    1. nums[i]为正数，前面没有乘积是正数的子数组（比如乘积是0或者负数或者没有任何数），这个时候nums[i]可以单独做一个子数组，positive[i] = 1。
    2. nums[i]为负数，前面没有乘积是负数的子数组，这个时候nums[i]单独作为子数组也不是正的，positive[i]是0。
  2. nums[i]为0时，positive[0]只能为0，因为单独让nums[i]成为子数组乘积是0，nums[i]跟前面子数组乘积相乘也是0。

positive[i]的状态转移方程

  1. nums[i] > 0 时：
     1. `positive[i] = positive[i - 1] + 1`，当 `i > 0 && positive[i - 1] > 0`，前面有乘积为正数的子数组，正数*正数乘积是正数
 2. `positive[i] = 1`，当`i > 0 && positive[i - 1] == 0`，前面没有乘积为正数的子数组，`nums[i]`单独作为一个子数组
  2. nums[i] < 0 时：
     1. `positive[i] = negative[i - 1] + 1`，当 `i > 0 && negative[i - 1] > 0`，前面有乘积为负数的子数组，负数*负数乘积是正数
 2. `positive[i] = 0`，当 `i > 0 && negative[i - 1] == 0`，前面没有乘积为负数的子数组，`nums[i]`没的乘，以`nums[i]`结尾的子数组的乘积没办法变为正数
  3. num[i] == 0 时：
    positive[i] = 0
  4. i == 0 时，positive[0] = if (nums[0] > 0) 1 else 0

如何保证以nums[i]结尾的子数组乘积为负数？

跟positive[i]正好相反。
nums[i]跟前面的子数组连接时：
1. nums[i]为正，前面子数组乘积为负
2. nums[i]为负，前面子数组乘积为正

negative[i]的状态转移方程

  1. nums[i] > 0 时：
     1.` i > 0 && negative[i - 1] > 0` 时，`negative[i] = negative[i - 1] + 1`
 2. `i > 0 && negative[i - 1] == 0` 时，`negative[i] = 0`
  2. nums[i] < 0 时：
     1. `i > 0 && positive[i - 1] > 0` 时，`negative[i] = positive[i - 1] + 1`
 2. `i > 0 && positive[i - 1] == 0` 时，`negative[i] = 1`
  3. num[i] == 0 时：
    negative[i] = 0
  4. i == 0 时，negative[0] = if (nums[0] < 0) 1 else 0

空间优化

positive[i]和negative[i]只与上一个状态有关，不需要数据存储所有状态，用变量记录上一个状态即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    fun getMaxLen(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) return 0
        var positive = if (nums[0] > 0) 1 else 0
        var negative = if (nums[0] < 0) 1 else 0
        var maxLength = positive
        for (i in 1 until n) {
            when {
                nums[i] > 0 -> {
                    positive = if (positive > 0) positive + 1 else /*if (positive == 0)*/ 1 
                    negative = if (negative > 0) negative + 1 else /*if (negative[i - 1] == 0)*/ 0 
                }
                nums[i] < 0 -> {
                    val newPositive = if (negative > 0) negative + 1 else /* if (negative == 0) */ 0
                    val newNegative = if (positive > 0) positive + 1 else /* if (positive == 0) */ 1
                    positive = newPositive
                    negative = newNegative
                }
                nums[i] == 0 -> {
                    positive = 0
                    negative = 0
                }
            }
            maxLength = maxOf(maxLength, positive)
        }
        return maxLength
    }
}