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 và hai giá trị chỉ số x và y. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm dãy con tăng tổng tối đa từ một tiền tố và một phần tử đã cho sau tiền tố phải trong C ++.
Mô tả vấn đề
Chúng tôi sẽ tìm tổng số tối đa của chuỗi tăng dần cho đến chỉ mục x và bao gồm phần tử ở chỉ mục y.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6 Đầu ra
26
Giải thích
Chúng tôi sẽ lấy dãy con cho đến chỉ mục 3 và cuối cùng là bao gồm arr [6] =11.
Dãy con là {1, 5, 9, 11}. Tổng =1 + 5 + 9 + 11 =26
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản là tạo một mảng mới cho đến chỉ mục x và sau đó thêm phần tử ở chỉ mục y vào cuối. Sau đó, tính toán tất cả các dãy con tăng dần và sau đó loại bỏ tất cả những gì không thể bao gồm phần tử arr [y] và tìm maxSum.
Một cách tiếp cận hiệu quả hơn để giải quyết vấn đề là sử dụng cách tiếp cận lập trình động. Ý tưởng là tạo mảng 2-D DP [] [] và lưu trữ tổng tối đa của dãy con tăng dần. Giá trị tại DP [x] [y] sẽ cho tổng lớn nhất cho đến khi chỉ số x bao gồm phần tử arr [y].
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][100];
void preCalcMaxSum(int arr[], int N){
for (int i = 0; i < N; i++) {
if (arr[i] > arr[0])
DP[0][i] = arr[i] + arr[0];
else
DP[0][i] = arr[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[j] > arr[i] && j > i) {
if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
DP[i][j] = DP[i - 1][i] + arr[j];
else
DP[i][j] = DP[i - 1][j];
}
else
DP[i][j] = DP[i - 1][j];
}
}
}
int main() {
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
preCalcMaxSum(arr, N);
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<DP[x][y];
return 0;
} Đầu ra
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
Một cách tiếp cận hiệu quả đang sử dụng để tìm tổng lớn nhất của dãy con tăng dần cho đến chỉ số x theo cách sao cho phần tử lớn nhất của dãy nhỏ hơn phần tử ở chỉ số y. Đối với điều này, chúng tôi sẽ lại sử dụng phương pháp lập trình động.
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 calcMaxSum(int arr[], int n, int x, int y){
int DP[x] = {0};
int maxSum = -1;
for (int i = 0; i <= x; i++)
DP[i] = arr[i];
for (int i = 0; i <= x; i++) {
if (arr[i] >= arr[y]) {
continue;
}
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j])
DP[i] += arr[j];
maxSum = max(maxSum, DP[i]);
}
}
if (maxSum == -1) {
return arr[y];
}
return maxSum + arr[y];
}
int main(){
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<calcMaxSum(arr, N, x, y);
return 0;
} Đầu ra
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26