Link đề:
https://oj.program.edu.vn/problem/ts07_daysolc
Tóm tắt đề:
Tìm dãy con có tính chất “lòng chảo” dài nhất trong dãy số nguyên đã cho. Một dãy số được gọi là lòng chảo nếu giảm dần từ đầu đến một điểm cực tiểu rồi tăng dần về sau với số phần tử trong đoạn giảm bằng số phần tử trong đoạn tăng. Dãy con này phải liên tiếp và có ít nhất 3 phần tử.
Hình dưới là minh họa cho các dãy lòng chảo trong mảng gồm các phần tử : 9,8,7,7,5,6,8,8,9,8,7,6,5,4,3,2,1,5,6,7
Gợi ý:
Dựa trên thông tin mô tả “Dãy dòng chảo“, ta gọi mid là vị trí tương đương với “điểm cực tiểu” của lòng chảo, left, right là vị trí bên trái và bên phải của mid, từ đó ta có thể dễ dàng nhận thấy: Dãy lòng chảo là dãy thỏa điều kiện:
$$A[left] \ge A[mid] \le A[right]$$
Từ nhận xét này ta có phương án như sau:
- Xét mọi vị trí i, nếu vị trí i thỏa điều kiện : \( A[i-1] \ge A[i] \le A[i+1] \)
- Đặt left = i-1 và right = i+1 rồi sử dụng kỹ thuật 2 con trỏ chạy ra 2 bên:
- Trong khi (left-1>0) và (A[left] <= A[left-1]): left = left -1
- Trong khi (right+1<=n) và (A[righ] <= A[right+1]): right = right + 1
- Khi kết thúc mở rộng vị trí left và right ta có độ dài dãy con sẽ là giá trị length = right – left + 1
- Cập nhật giá trị MaxLength dựa trên giá trị của length để có được kết quả cuối cùng theo yêu cầu bài toán.