個人主頁：元清加油_【C++】,【C語言】,【數據結構與算法】-CSDN博客

個人專欄

力扣遞歸算法題

?http://t.csdnimg.cn/yUl2I

【C++】? ??

??????http://t.csdnimg.cn/6AbpV

數據結構與算法

????http://t.csdnimg.cn/hKh2l

前言：這個專欄主要講述動態規劃算法，所以下面題目主要也是這些算法做的 ?

我講述題目會把講解部分分為3個部分：
1、題目解析

2、算法原理思路講解

3、代碼實現

乘積為正數的最長子數組長度

題目鏈接：乘積為正數的最長子數組長度

題目

給你一個整數數組?nums?，請你求出乘積為正數的最長子數組的長度。

一個數組的子數組是由原數組中零個或者更多個連續數字組成的數組。

請你返回乘積為正數的最長子數組長度。

示例? 1：

輸入：nums = [1,-2,-3,4]
輸出：4
解釋：數組本身乘積就是正數，值為 24 。

示例 2：

輸入：nums = [0,1,-2,-3,-4]
輸出：3
解釋：最長乘積為正數的子數組為 [1,-2,-3] ，乘積為 6 。
注意，我們不能把 0 也包括到子數組中，因為這樣乘積為 0 ，不是正數。

示例 3：

輸入：nums = [-1,-2,-3,0,1]
輸出：2
解釋：乘積為正數的最長子數組是 [-1,-2] 或者 [-2,-3] 。

提示：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i]?<= 10^9

解法

算法原理解析

我們這題使用動態規劃，我們做這類題目可以分為以下五個步驟

1. 狀態顯示
2. 狀態轉移方程
3. 初始化（防止填表時不越界）
4. 填表順序
5. 返回值

• 狀態顯示

• 狀態轉移方程

1. nums[i] = 0 時，所有以 i 為結尾的?數組的乘積都不可能是正數，此時 f[i] = 0 ；
2. nums[i] > 0 時，那么直接找到 f[i - 1] 的值（這?請再讀?遍 f[i - 1] 代表的意義，并且考慮如果 f[i - 1] 的結值是 0 的話，影不影響結果），然后加?即可，此時 f[i] = f[i - 1] + 1 ；
3. nums[i] < 0 時，此時我們要看 g[i - 1] 的值（這?請再讀?遍 g[i - 1] 代 表的意義。因為負負得正，如果我們知道以 i - 1 為結尾的乘積為負數的最??數組的?度，加上 1 即可），根據 g[i - 1] 的值，?要分兩種情況：
   1. g[i - 1] = 0 ，說明以 i - 1 為結尾的乘積為負數的最??數組是不存在的，又因為 nums[i] < 0 ，所以以 i 結尾的乘積為正數的最??數組也是不存在的，此時 f[i] = 0 ；
   2. g[i - 1] != 0 ，說明以 i - 1 為結尾的乘積為負數的最??數組是存在的，又因為 nums[i] < 0 ，所以以 i 結尾的乘積為正數的最??數組就等于 g[i - 1] + 1 ；

• 初始化（防止填表時不越界）

• 填表順序

• 返回值

class Solution {
public:int getMaxLen(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1);		// 以i為結尾，乘積為正數的最長子數組vector<int> g(n + 1);		// 以i為結尾，乘積為負數的最長子數組// 初始化f[0] = 0;g[0] = 0;int ans = INT_MIN;for (int i = 1; i <= n; i++){if (nums[i-1] > 0){f[i] = f[i - 1] + 1;g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;}else if (nums[i-1] < 0){f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;g[i] = f[i - 1] + 1;}ans = max(ans, f[i]);}return ans;}
};