DDSA Solutions

3105. Longest Strictly Increasing or Strictly Decreasing Subarray

EasyView on LeetCode
Array
Time: O(n)
Space: O(1)

Problem Overview

Find longest strictly increasing then strictly decreasing subarray.

Intuition

Find longest strictly increasing then strictly decreasing subarray. DP on both directions.

Algorithm

  1. 1inc[i] = length of longest strictly increasing ending at i. dec[i] = longest strictly decreasing starting at i.
  2. 2Answer = max(inc[i] + dec[i] - 1) where both > 1 (actual peak).

Common Pitfalls

  • •Peak must have both inc and dec > 1. Maximum mountain length.
3105.cs
C#
// Approach: Track current run lengths for both increasing and decreasing; update max.
// Time: O(n) Space: O(1)

public class Solution
{
    public int LongestMonotonicSubarray(int[] nums)
    {
        int ans = 1;
        int increasing = 1;
        int decreasing = 1;

        for (int i = 1; i < nums.Length; ++i)
        {
            if (nums[i] > nums[i - 1])
            {
                increasing += 1;
                decreasing = 1;
            }
            else if (nums[i] < nums[i - 1])
            {
                decreasing += 1;
                increasing = 1;
            }
            else
            {
                increasing = 1;
                decreasing = 1;
            }
            ans = Math.Max(ans, Math.Max(increasing, decreasing));
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems