Untitled

 avatar
unknown
plain_text
2 years ago
1.6 kB
60
Indexable
/*

Дан массив чисел a_1, a_2, ..., a_n .
Необходимо найти монотонный подотрезок (то есть строго убывающий или строго возрастающий) 
максимальной длины и вернуть пару индексов его начала и конца.

[2, 7, 5, 4, 4, 3] -> {1, 3}
[1, 1] -> {1, 1} // or {0, 0}

*/

public (int, int) FindLongestSubArray(int[] arr)
{
    if (arr == null || arr.Length == 0)
        return (-1, -1);
    if (arr.Length == 1)
        return (0, 0);
    var l = 0; // 5
    var r = 0; // 5
    var max_length = 0; // 2
    var best_l = 0; // 1
    var best_r = 0; // 3

    while (r < arr.Length - 1) // 6
    {
        r = l + 1; // l = 0, r = 1
        if (arr[r] > arr[l])
        {
            while (r < arr.Length && arr[r] > arr[r - 1])
                r++; // r = 2
            r--;
            if (r - l > max_length)
            {
                max_length = r - l;
                best_l = l;
                best_r = r;
            }
            l = r;
        }else if (arr[r] < arr[l]){
            while (r < arr.Length && arr[r] < arr[r - 1])
                r++;
            r--;
            if (r - l > max_length)
            {
                max_length = r - l;
                best_l = l;
                best_r = r;
            }
            l = r;
        }else{
            l++;
            r = l;
        }
    }

    return (best_l, best_r);
}

[1, 3] -> {0, 1}
[3, 1] -> {0, 1}
[2, 7, 5, 4, 4, 3] -> {1, 3}
[7, 2, 5, 4, 4, 3]
Editor is loading...