Revise paste Untitled

//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution {
	public:
	int dp[100001][2];
    vector<int> arr;
int rec1(int at, bool count){
    if(dp[at][count] != -1){
        return dp[at][count];
    }
    int res = 0;
    for(int i = at + 1; i < arr.size(); i++){
        if(arr[i] < arr[at] && count == true){
            res = max(res, rec1(i, false) + 1);
        }
        if(arr[i] > arr[at] && count == false){
            res = max(res, rec1(i, true) + 1);
        }
    }
    
    return dp[at][count] = res;
}
		int ZigZagMaxLength(vector<int>&nums){
        memset(dp, -1, sizeof dp);
        arr = nums;
        int res = 0;
        for(int i = 0; i < nums.size(); i++) {
            res = max(res, rec1(i, 0) + 1);
            res = max(res, rec1(i, 1) + 1);
            
        }
        return res;
		}

};

//{ Driver Code Starts.
int main(){
	int tc;
	cin >> tc;
	while(tc--){
		int n;
		cin >> n;
		vector<int>nums(n);
		for(int i = 0; i < n; i++)
			cin >> nums[i];
		Solution obj;
		int ans = obj.ZigZagMaxLength(nums);
		cout << ans << "\n";
	
cout << "~" << "\n";
}
	return 0;
}
// } Driver Code Ends