Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n. Nhiệm vụ của chúng ta là tạo chương trình ứng dụng để tìm Chuỗi con tăng tổng tối đa bằng cách sử dụng DP trong C ++.
Mô tả sự cố - Để tìm dãy con tăng tổng lớn nhất, chúng ta sẽ tạo dãy con trong đó phần tử tiếp theo lớn hơn phần tử hiện tại.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 2, 3, 6, 5, 9} Đầu ra
20
Giải thích
Increasing subsequence with maximum sum:
{2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20 Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề bằng cách sử dụng Phương pháp tiếp cận chương trình động. Chúng tôi sẽ tạo anarray để lưu trữ tổng tối đa cho đến phần tử hiện tại. Sau đó, trả về themaxSum từ mả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 retMaxVal(int x, int y){
if(x > y)
return x;
return y;
}
int calcMaxSubSeqSum(int arr[], int n) {
int maxSum = 0;
int sumDP[n];
for (int i = 0; i < n; i++ )
sumDP[i] = arr[i];
for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( (sumDP[i] < (sumDP[j] + arr[i])) && ( arr[i] >
arr[j] ) )
sumDP[i] = sumDP[j] + arr[i];
for (int i = 0; i < n; i++ )
maxSum = retMaxVal(sumDP[i], maxSum);
return maxSum;
}
int main() {
int arr[] = {4, 2, 3, 6, 5, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum Sum Increasing Subsequence using DP is
"<<calcMaxSubSeqSum(arr, n);
return 0;
} Đầu ra
Sum of maximum sum increasing subsequence is 20