乘积为正数的最长子数组长度

题目描述：

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

输入：

第一行一个整数n,表示数组长度；第二行n个数mi,表示数组元素。

输出：

一个整数，表示最长长度。

样例输入：

4

1 -2 -3  4

样例输出：

4

提示：

1<=n<=105（10的5次方）

-109（负10的9次方）<=mi<=109（10的9次方）

这题实在不会，看了大佬的题解写出来的。

用贪心来写这道题，比起动规还要维护两个数组方便多了。

我们来搞三个变量，pos,neg,first.pos表示当前遇到的数是整数，那么pos就加一；如果遇到的是负数，我先用first记录第一个负数出现的位置，然后neg加一；如果遇到的数是0，那么三个变量全部初始化为最开始的值，因为任何一个段中都不可能包含0.

用first记录某一个段中第一个负数出现的位置，因为碰到了负数，肯定就不符合题目要求了，但是，万一后面又碰到负数了呢？我再拿后面那个可能碰到的负数的位置减去first记录的第一个出现负数的位置，不就是一个新的长度吗？再拿去和现有的长度比较谁更长就行了。

对于neg,如果是偶数，那么肯定乘积是整数，pos+neg就是一个长度，和原有长度相比选较大的那个；若是奇数，表示目前为止只出现了一个负数，那么就需要统计一个新的长度，这个新的长度的起始位置就是记录的第一个负数出现的位置，我拿现在的位置减去记录的第一个负数出现的位置就是一个新的长度，拿去和原来的相比。

然后这事儿就成了！

贴一波代码：

 1 package com.hw.testdemo;
 2 
 3 import java.util.Scanner;
 4 
 5 public class MaxLen {
 6     public int getMaxLen(int[] nums) {
 7         int pos = 0;
 8         int neg = 0;
 9         int first = -1;
10         int ans = 0;
11         for (int i = 0; i < nums.length; ++i) {
12             if (nums[i] == 0) {
13                 pos = 0;
14                 neg = 0;
15                 first = -1;
16             } else if (nums[i] > 0) {
17                 pos++;
18             } else {
19                 if (first == -1) {
20                     first = i;
21                 }
22                 neg++;
23             }
24             if (neg % 2 == 0) {
25                 ans = Math.max(ans, pos + neg);
26             } else {
27                 ans = Math.max(ans, i - first);
28             }
29         }
30         return ans;
31     }
32     public static void main(String[] args) {
33         Scanner s = new Scanner(System.in);
34         int n = s.nextInt();
35         int[] nums = new int[n+1];
36         for (int i = 0; i < n; ++i) {
37             nums[i] = s.nextInt();
38         }
39         int ans = new MaxLen().getMaxLen(nums);
40         System.out.println(ans);
41         s.close();
42     }
43 }