Trong bài toán này, chúng ta được cung cấp một mảng arr []. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Tổng tối đa sao cho không có hai phần tử nào liền nhau trong C ++.
Mô tả vấn đề
Chúng ta cần tìm tổng lớn nhất của dãy từ mảng sao cho không có 2 số nào từ dãy tổng là liền nhau trong mảng.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {5, 1, 3, 7, 9, 2, 5} Đầu ra
22
Giải thích
Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22 Taking sum sequence from index 1 with alternate elements : 1 + 7 + 2 = 10
Phương pháp tiếp cận giải pháp
Trong tập trước, chúng ta đã thấy một cách tiếp cận để giải quyết vấn đề. Ở đây, chúng ta sẽ tìm hiểu về phương pháp lập trình động để giải quyết vấn đề.
Để giải quyết vấn đề bằng cách sử dụng Phương pháp tiếp cận động, chúng ta cần tạo một mảng DP [] để lưu trữ tổng tối đa đó cho đến chỉ mục hiện tại. Và sau đó tìm chỉ số tổng bằng cách sử dụng mảng động này.
DP tối đa hiện tại là giá trị tối đa của dp [i + 2] + arr [i] và dp [i + 1].
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 <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSumWOAdj(int arr[], int i, int n){
if (i >= n)
return 0;
if (currState[i])
return DP[i];
currState[i] = 1;
DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
return DP[i];
}
int main(){
int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
int n = sizeof(arr) / sizeof(int);
cout<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
return 0;
} Đầu ra
The maximum sum such that no two elements are adjacent is 22