Longest Turbulent Subarray - Fibonacci's Approach

Problem is here: https://leetcode.com/problems/longest-turbulent-subarray/
978. Longest Turbulent Subarray
Medium
A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:
  • For i <= k < jA[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
  • OR, for i <= k < jA[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.
That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
Return the length of a maximum size turbulent subarray of A.

Example 1:
Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])
Example 2:
Input: [4,8,12,16]
Output: 2
Example 3:
Input: [100]
Output: 1

Note:
  1. 1 <= A.length <= 40000
  2. 0 <= A[i] <= 10^9
Use same approach used to calculate the Nth Fibonacci's number:keep track of the previous value and calculate the current. Along the way, keep track of the best (longest) so far. Your previous become current. Keep going, O(n)-time, O(1)-space. Code's below, cheers, ACC.


public class Solution
{
    public int MaxTurbulenceSize(int[] A)
    {
        if (A == null) return 0;
        if (A.Length == 1) return 1;
        if (A.Length == 2)
        {
            if (A[0] == A[1]) return 1;
            else return 2;
        }

        int prev = (A[0] == A[1]) ? 1 : 2;
        int best = prev;
        for (int i = 2; i < A.Length; i++)
        {
            int current = 0;
            if (A[i] == A[i - 1])
            {
                current = 1;
            }
            else
            {
                if (A[i] > A[i - 1])
                {
                    if (A[i - 1] >= A[i - 2])
                    {
                        current = 2;
                    }
                    else
                    {
                        current = 1 + prev;
                    }
                }
                else
                {
                    if (A[i - 1] <= A[i - 2])
                    {
                        current = 2;
                    }
                    else
                    {
                        current = 1 + prev;
                    }
                }
            }

            best = Math.Max(best, current);
            prev = current;
        }

        return best;
    }
}

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons