算法题解：求一个数组中正数和负数交替出现的最长子数组（JAVA代码）

Q1. 求一个数组中正数和负数交替出现的最长子数组（JAVA代码）

条件：数组中只包含正数和负数

例如：给定数组 a[] = {-5, -1, -1, 2, -2, -3}
输出结果为：3 
最长子数组是： {-1, 2, -2} 

给定数组：a[] = {1, -5, 1, -5}
输出结果是：4

---

算法设计

package com.bean.algorithm.arrays;

public class LongestAlternatingSubarray {

	static int findSubarray(int a[], int n) {

		int longest = 1;
		int cnt = 1;

		// 遍历数组元素
		for (int i = 1; i < n; i++) {

			// 检查正数和负数交替出现
			if (a[i] * a[i - 1] < 0) {
				cnt++;
				longest = Math.max(longest, cnt);
			} else
				cnt = 1;
		}
		return longest;
	}

	
	public static void main(String[] args) {
		int a[] = { -5, -1, -1, 2, -2, -3 };
		int n = a.length;

		System.out.println(findSubarray(a, n));
	}
}

程序运行结果：

3

---

Q2. 求一个数组中从任意下标i开始正数和负数交替出现的最长子数组的长度（JAVA代码）

问题变化一下，增加一个条件，从数组中任意下标 i 开始，求正数和负数交替出现的最长子数组的长度。

例如：

给定数组：a[] = {1, -5, 1, -5}

输出结果：

对于下标 0, {1, -5, 1, -5} = 4

对于下标 1, {-5, 1, -5} = 3

对于下标 2, {1, -5} = 2

对于下标 3, {-5} = 1.
      
给定数组：a[] = {-5, -1, -1, 2, -2, -3}

输出结果：

下标 0 = 1,
下标 1 = 1,
下标 2 = 3,
下标 3 = 2,
下标 4 = 1,
下标 5 = 1,

---

算法设计

package com.bean.algorithm.arrays;

public class LongestAlternatingSubarrayExt {

	public static void longestAlternating(int arr[], int n) {
		int[] count = new int[n];

		count[n - 1] = 1;
		for (int i = n - 2; i >= 0; i--) {
			if (arr[i] * arr[i + 1] < 0) {
				count[i] = count[i + 1] + 1;
			} else {
				count[i] = 1;
			}

		}

		for (int i = 0; i < n; i++) {
			System.out.println(count[i] + " ");
		}
	}

	public static void main(String[] args) {
		int a[] = { -5, -1, -1, 2, -2, -3 };
		int n = 6;
		longestAlternating(a, n);
	}
}

程序运行结果：

1 
1 
3 
2 
1 
1