The Longest Alternating Subarray problem asks for finding the longest subarray in an array where the adjacent elements are alternating in sign, that is, positive and negative.
To solve this problem using dynamic programming, we can define an array ‘dp‘ where ‘dp[i]‘ represents the length of the longest alternating subarray ending at index ‘i‘. We can start by initializing ‘dp[i]‘ to ‘1‘ for all indices since a single element array can be considered as an alternating subarray.
Next, we can traverse the array from left to right, updating ‘dp[i]‘ based on the values of ‘dp[i-1]‘ and the sign of the current and previous elements. If the current and previous elements have opposite signs, we can extend the alternating subarray ending at index ‘i-1‘ by adding the current element, resulting in a new alternating subarray ending at index ‘i‘ with a length of ‘dp[i-1] + 1‘. If the current and previous elements have the same sign, we can only include the current element as a new possible start for a new alternating subarray of length ‘1‘.
Finally, we can return the maximum value in the ‘dp‘ array as the length of the longest alternating subarray.
Here’s the Java code implementing this approach:
public int longestAlternatingSubarray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
if (nums[i] * nums[i-1] < 0) {
dp[i] = dp[i-1] + 1;
maxLen = Math.max(maxLen, dp[i]);
} else {
dp[i] = 1;
}
}
return maxLen;
}Let’s illustrate this approach with an example:
Input: nums = [1, -2, 3, 4, -5, 6, 7, -8, -9, 10]
Output: 5 i 0 1 2 3 4 5 6 7 8 9
nums [1, -2, 3, 4, -5, 6, 7, -8, -9, 10]
dp [1, 2, 1, 2, 3, 4, 5, 2, 3, 4]Initially, we have ‘dp = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]‘. Then, we start traversing the array from left to right:
- At index ‘i=1‘, we have ‘nums[i] * nums[i-1] < 0‘, so we can extend the alternating subarray ending at index ‘i-1‘ by adding the current element. Therefore, we set ‘dp[i] = dp[i-1] + 1 = 2‘ and ‘maxLen = 2‘.
- At index ‘i=2‘, we have ‘nums[i] * nums[i-1] > 0‘, so we can only include the current element as a new possible start for a new alternating subarray of length ‘1‘. Therefore, we set ‘dp[i] = 1‘.
- At index ‘i=3‘, we have ‘nums[i] * nums[i-1] < 0‘, so we can extend the alternating subarray ending at index ‘i-1‘ by adding the current element. Therefore, we set ‘dp[i] = dp[i-1] + 1 = 2‘.
- At index ‘i=4‘, we have ‘nums[i] * nums[i-1] > 0‘, so we can only include the current element as a new possible start for a new alternating subarray of length ‘1‘. Therefore, we set ‘dp[i] = 1‘.
- At index ‘i=5‘, we have ‘nums[i] * nums[i-1] < 0‘, so we can extend the alternating subarray ending at index ‘i-1‘ by adding the current element. Therefore, we set ‘dp[i] = dp[i-1] + 1 = 4‘ and ‘maxLen = 4‘.
- At index ‘i=6‘, we have ‘nums[i] * nums[i-1] < 0‘, so we can extend the alternating subarray ending at index ‘i-1‘ by adding the current element. Therefore, we set ‘dp[i] = dp[i-1] + 1 = 5‘ and ‘maxLen = 5‘.
- At index ‘i=7‘, we have ‘nums[i] * nums[i-1] > 0‘, so we can only include the current element as a new possible start for a new alternating subarray of length ‘1‘. Therefore, we set ‘dp[i] = 1‘.
- At index ‘i=8‘, we have ‘nums[i] * nums[i-1] > 0‘, so we can only include the current element as a new possible start for a new alternating subarray of length ‘1‘. Therefore, we set ‘dp[i] = 1‘.
- At index ‘i=9‘, we have ‘nums[i] * nums[i-1] < 0‘, so we can extend the alternating subarray ending at index ‘i-1‘ by adding the current element. Therefore, we set ‘dp[i] = dp[i-1] + 1 = 2‘.
Finally, we return ‘maxLen = 5‘, which is the length of the longest alternating subarray in ‘nums‘.