Solve the problem of finding the Longest Zig-Zag Subsequence using dynamic programming.?

The Longest Zig-Zag Subsequence problem is to find the length of the longest subsequence of a given sequence such that the subsequence alternates between increasing and decreasing elements.

For example, given a sequence [1, 7, 4, 9, 2, 5], the longest zig-zag subsequence would be [1, 7, 4, 9, 2].

To solve this problem using dynamic programming, we can use a 2-dimensional array dp[i][j], where dp[i][j] represents the length of the longest zig-zag subsequence ending at i with the last element as j.

We can start by initializing all the elements of the dp array to 1, since the longest zig-zag subsequence at any index i with the last element as j would be 1.

Then, for each index i and each element j before i, we can check if the difference between j and i has a different sign than the difference between i and the previous element in the subsequence. If so, we can update dp[i][j] to be the maximum of dp[i][j] and dp[k][j] + 1, where k is the index of the previous element in the subsequence.

In Java, the code would look like this:

public int longestZigZagSubsequence(int[] nums) {
    int n = nums.length;
    int[][] dp = new int[n][2];
    for (int i = 0; i < n; i++) {
        dp[i][0] = dp[i][1] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[i][0] < dp[j][1] + 1) {
                dp[i][0] = dp[j][1] + 1;
            }
            if (nums[j] > nums[i] && dp[i][1] < dp[j][0] + 1) {
                dp[i][1] = dp[j][0] + 1;
            }
        }
    }
    return Math.max(dp[n - 1][0], dp[n - 1][1]);
}

In this implementation, we use dp[i][0] to represent the length of the longest zig-zag subsequence ending at i with the last element as a decreasing element, and dp[i][1] to represent the length of the longest zig-zag subsequence ending at i with the last element as an increasing element.

We iterate through each index i of the array, and for each index i, we iterate through all the elements j before i. We then update dp[i][0] and dp[i][1] based on whether nums[j] is less than or greater than nums[i], and whether the difference between j and i has a different sign than the difference between i and the previous element in the subsequence.

Finally, we return the maximum of dp[n - 1][0] and dp[n - 1][1], which represents the length of the longest zig-zag subsequence ending at the last element of the array.