Longest Strictly Increasing or Strictly Decreasing Subarray

Leetcode Problem:

• Longest Strictly Increasing or Strictly Decreasing Subarray

Summary

• Find the length of the longest strictly increasing or decreasing subarray in a given array of integers.

Approach

• The solution uses a dynamic programming approach
• It maintains two variables, inc and dec, to track the length of the longest increasing and decreasing subarrays ending at the current position
• The maximum length between these two subarrays is updated at each step.

Complexity

• O(n), where n is the length of the input array
• This is because the solution iterates through the array once.

Explain

• The solution starts by initializing three variables: inc, dec, and ans
• inc and dec are used to track the length of the longest increasing and decreasing subarrays ending at the current position, respectively
• ans is used to store the maximum length of these subarrays
• The solution then iterates through the array, updating inc and dec based on whether the current element is greater than or less than the previous element
• If the current element is equal to the previous element, inc and dec are reset to 1
• At each step, the solution updates ans to be the maximum of its current value and the maximum of inc and dec
• Finally, the solution returns ans, which represents the length of the longest strictly increasing or decreasing subarray in the input array.

Solution Code:

class Solution {
public:
    int longestMonotonicSubarray(vector& nums) {
        int inc = 1;
        int dec = 1;
        int ans = 1;
        for(int i = 1 ; i < nums.size(); i++){
            if (nums[i-1] < nums[i]){
                inc++;
                dec = 1;
            }else if (nums[i-1] > nums[i]){
                inc = 1;
                dec++;
            } else{
                dec = 1;
                inc = 1;
            }
            
            ans = max(ans, max(inc, dec));
        }
        return ans;
    }
};