978. Longest Turbulent Subarray

LeetCode medium original: C# #array #csharp #leetcode #math #medium

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Дан integer array arr, return длину максимального турбулентного подarrayа arrayа arr.

Подarray считается турбулентным, если знак сравнения меняется между каждой парой смежных elementов в подarrayе.

Более формально, подarray [arr[i], arr[i + 1], ..., arr[j]] arrayа arr считается турбулентным тогда и только тогда, когда:

Для всех i <= k < j:

arr[k] > arr[k + 1], когда k нечетное, и

arr[k] < arr[k + 1], когда k четное.

Или, для всех i <= k < j:

arr[k] > arr[k + 1], когда k четное, и

arr[k] < arr[k + 1], когда k нечетное.

Example:

Input: arr = [9,4,2,10,7,8,8,1,9]

Output: 5

Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

C# solution

matched/original

public class Solution {
    public int MaxTurbulenceSize(int[] A) {
        int N = A.Length;
        int ans = 1;
        int anchor = 0;
        for (int i = 1; i < N; ++i) {
            int c = Math.Sign(A[i - 1] - A[i]);
            if (c == 0) {
                anchor = i;
            } else if (i == N - 1 || c * Math.Sign(A[i] - A[i + 1]) != -1) {
                ans = Math.Max(ans, i - anchor + 1);
                anchor = i;
            }
        }
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxTurbulenceSize(vector<int>& A) {
        int N = A.size();
        int ans = 1;
        int anchor = 0;
        for (int i = 1; i < N; ++i) {
            int c = Math.Sign(A[i - 1] - A[i]);
            if (c == 0) {
                anchor = i;
            } else if (i == N - 1 || c * Math.Sign(A[i] - A[i + 1]) != -1) {
                ans = max(ans, i - anchor + 1);
                anchor = i;
            }
        }
        return ans;
    }
}

Java solution

matched/original

class Solution {
    public int maxTurbulenceSize(int[] A) {
        int N = A.length;
        int ans = 1;
        int anchor = 0;

        for (int i = 1; i < N; ++i) {
            int c = Integer.compare(A[i - 1], A[i]);
            if (c == 0) {
                anchor = i;
            } else if (i == N - 1 || c * Integer.compare(A[i], A[i + 1]) != -1) {
                ans = Math.max(ans, i - anchor + 1);
                anchor = i;
            }
        }

        return ans;
    }
}

JavaScript solution

matched/original

var maxTurbulenceSize = function(A) {
    const N = A.length;
    let ans = 1;
    let anchor = 0;

    for (let i = 1; i < N; ++i) {
        const c = Math.sign(A[i - 1] - A[i]);
        if (c === 0) {
            anchor = i;
        } else if (i === N - 1 || c * Math.sign(A[i] - A[i + 1]) !== -1) {
            ans = Math.max(ans, i - anchor + 1);
            anchor = i;
        }
    }

    return ans;
};

Go solution

matched/original

func maxTurbulenceSize(A []int) int {
    N := len(A)
    ans := 1
    anchor := 0

    for i := 1; i < N; i++ {
        c := compare(A[i-1], A[i])
        if c == 0 {
            anchor = i
        } else if i == N-1 || c*compare(A[i], A[i+1]) != -1 {
            if i-anchor+1 > ans {
                ans = i - anchor + 1
            }
            anchor = i
        }
    }

    return ans
}

func compare(a, b int) int {
    if a > b {
        return 1
    }
    if a < b {
        return -1
    }
    return 0
}

Algorithm

Сканируйте array слева направо. Используйте переменные для отслеживания начала текущего блока и максимальной длины турбулентного подarrayа.

Если достигли конца блока (последний element или текущий element не соответствует условию чередования), зафиксируйте длину этого блока как потенциальный ответ и установите начало нового блока на следующий element.

Повторяйте шаг 2 до конца arrayа и return максимальную длину турбулентного подarrayа.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.