Untitled
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...