Tổng số con tối đa sao cho không có ba con nào liên tiếp 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 ta là tạo một chương trình để tìm tổng số con lớn nhất sao cho không có ba nào liên tiếp nhau.

Mô tả sự cố - Ở đây, chúng ta cần tìm tổng các dãy được tạo từ mảng sao cho không có ba phần tử liên tiếp.

Các phần tử liên tiếp của mảng là những phần tử tuân theo cùng một thứ tự chỉ mục.

 arr [0], arr [1], arr [2],… 

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

 arr [] ={5, 9, 12, 15} 

Đầu ra

 32 

Giải thích

 Sum =5 + 12 + 15 =32 

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tạo một mảng bổ trợ để lưu trữ tổng cho đến chỉ mục hiện tại. Và sau đó tìm tổng và kiểm tra tổng cho đến chỉ mục bằng cách kiểm tra các tổng liên tiếp.

 Đối với hai giá trị tổng đầu tiên, sumVal [0] =arr [0] sumVal [1] =arr [0] + arr [1] 

Khi đó giá trị thứ ba cần xét không thể được xét trực tiếp. Và khi xem xét tổng, chúng tôi sẽ kiểm tra các điều kiện với ba hiện tại, Nếu xem xét arr [i], làm tăng giá trị tổng, loại trừ arr [i − 1] hoặc arr [i − 2]. ], tổng vẫn giữ nguyên.

 sum [i] =max (sum [i − 3] + arr [i − 1] + arr [i], sum [i − 2] + arr [i], sum [i − 1])  
 Ví dụ 
 

  Chương trình hiển thị việc triển khai giải pháp của chúng tôi,  
 
 #include  using namespace std; int findMaxSubSeqSum (int arr [], int n) {int maxSumArr [n]; maxSumArr [0] =arr [0]; maxSumArr [1] =arr [0] + arr [1]; maxSumArr [2] =max (maxSumArr [1], max (arr [1] + arr [2], arr [0] + arr [2])); for (int i =3; i  
 Đầu ra 
 
 Tổng số con tối đa sao cho không có ba nào liên tiếp là 32