Tích tối đa của dãy con có kích thước 3 ngày càng tăng trong chương trình C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n số nguyên dương. Nhiệm vụ của chúng tôi là tạo ra một chương trình để tìm ra sản phẩm Tối đa của một nhóm nhỏ ngày càng tăng có kích thước 3.

Mô tả sự cố - Ở đây, chúng ta cần tìm tích tối đa của 3 phần tử của mảng sao cho chúng tạo thành một dãy con tăng dần và chỉ số mảng cũng tăng lên tức là

 arr [i] * arr [j] * arr [k] là tối đa, arr [i]  

  Hãy lấy một ví dụ để hiểu vấn đề,  
 
 Đầu vào 
 
 arr ={5, 9, 2, 11, 4, 7} 
 
 Đầu ra 
 
 495 
 
 Giải thích 
 
 Tất cả các mảng con có kích thước 3 thỏa mãn điều kiện là (5, 9, 11), prod =5 * 9 * 11 =495 (2, 4, 7), prod =2 * 4 * 7 =56Maximum =495  
 Phương pháp tiếp cận giải pháp 
 

 Một cách đơn giản để giải quyết vấn đề là lặp lại mảng và tìm tất cả các mảng con của 3 thỏa mãn điều kiện đã cho. 
 

 Tìm sản phẩm của các phần tử và trả về giá trị tối đa của tất cả các sản phẩm. 
 
 Thuật toán 
 

  Khởi tạo  - 
 
 maxProd =−1000 
 

  Bước 1  - 
 
 Vòng lặp i -> 0 đến n − 3 
 

  Bước 1.1  - 
 
 Vòng lặp j -> i đến n − 2 
 

  Bước 1.1.1  - 
 
 if (arr [i]  vòng lặp k -> j đến n − 1 
 

  Bước 1.1.1.1  - 
 
 if (arr [j]  find prod =arr [i] * arr [j] * arr [k]. 
 

  Bước 1.1.1.2  - 
 
 if (maxProd> prod) -> maxProd =prod. 
 

  Bước 2  - 
 
 Trả lại maxProd. 
 
 Ví dụ 
 

  Chương trình minh họa hoạt động của giải pháp của chúng tôi,  
 
 #include  using namespace std; int calcMaxProd (int arr [], int n) {int maxProd =−1000; int prod; for (int i =0; i  
 Đầu ra 
 
 Tích tối đa của một phân con ngày càng tăng của kích thước 3 là 495 
 

 Giải pháp này dễ dàng nhưng sử dụng 3 vòng lặp lồng nhau làm cho độ phức tạp về thời gian của thứ tự O (n3). Vì vậy, chúng ta hãy xem một giải pháp hiệu quả cho vấn đề, 
 

 Trong giải pháp này, chúng ta sẽ lấy các phần tử của mảng từ chỉ số 1 đến n − 2. Và coi nó như phần tử giữa của mảng con 3 phần tử của chúng ta. Và sau đó tìm hai phần tử còn lại từ mảng. 
 
 Phần tử nhỏ hơn arr [i] trong mảng có chỉ số nhỏ hơn i. Phần tử lớn hơn aar [i] trong mảng có chỉ số hơn i. 
 

 Phần tử nhỏ nhất được tìm thấy bằng cách sử dụng cây tìm kiếm nhị phân tự cân bằng và đối với phần tử lớn nhất, chúng tôi sẽ duyệt từ phải sang trái và tìm phần tử lớn nhất ở bên phải. 
 

 Sau khi tìm thấy cả hai giá trị, chúng tôi sẽ tìm tiền đề của mảng con phần tử và sau đó tìm maxProd bằng cách so sánh tất cả. 
 
 Ví dụ 
 

  Chương trình minh họa hoạt động của giải pháp của chúng tôi,  
 
 #include  using namespace std; long calMaxSubSeqProd (int arr [], int n) {int smallLeftEle [n]; smallLeftEle [0] =−1; set  nhỏ; for (int i =0; i  =1; i−−) {if (arr [i]> greatRightEle) greatRightEle =arr [i]; else if (smallLeftEle [i]! =−1) {prod =smallLeftEle [i] * arr [i] * greatRightEle; if (prod> maxProd) maxProd =prod; }} return maxProd;} int main () {int arr [] ={5, 9, 2, 11, 4, 7}; int n =sizeof (arr) / sizeof (arr [0]); cout <<"Tích tối đa của dãy con tăng dần có kích thước 3 là" < 
 Đầu ra 
 
 Tích tối đa của một phân con ngày càng tăng của kích thước 3 là 495