ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม N และค่าดัชนีสองค่า x และ y งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดที่เพิ่มขึ้นจากคำนำหน้าและองค์ประกอบที่กำหนดหลังจากคำนำหน้าจะต้องอยู่ใน C ++
คำอธิบายปัญหา
เราจะหาผลรวมสูงสุดของลำดับที่เพิ่มขึ้นจนถึงดัชนี x และรวมองค์ประกอบที่ดัชนี y
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6 ผลลัพธ์
26
คำอธิบาย
เราจะใช้ลำดับต่อไปจนถึงดัชนี 3 และสุดท้ายรวม arr[6] =11
ลำดับถัดมาคือ {1, 5, 9, 11} ผลรวม =1+5+9+11 =26
แนวทางการแก้ปัญหา
วิธีง่ายๆ คือการสร้างอาร์เรย์ใหม่จนถึงดัชนี x แล้วเพิ่มองค์ประกอบที่ดัชนี y ต่อท้าย จากนั้นคำนวณลำดับย่อยที่เพิ่มขึ้นทั้งหมด แล้วทิ้งทั้งหมดที่ไม่สามารถรวมองค์ประกอบ arr[y] และหาค่า maxSum
แนวทางที่มีประสิทธิภาพอีกวิธีหนึ่งในการแก้ปัญหาคือการใช้แนวทางการเขียนโปรแกรมแบบไดนามิก แนวคิดคือการสร้างอาร์เรย์ 2 มิติ DP[][] และเก็บผลรวมสูงสุดของการเพิ่มลำดับย่อย ค่าที่ DP[x][y] จะให้ผลรวมสูงสุดจนถึงดัชนี x รวมถึงองค์ประกอบ arr[y].
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
แนวทางที่มีประสิทธิภาพ กำลังใช้เพื่อค้นหาผลรวมสูงสุดของการเพิ่มลำดับย่อยจนถึงดัชนี x ในลักษณะที่องค์ประกอบที่ใหญ่ที่สุดของลำดับนั้นน้อยกว่าองค์ประกอบที่ดัชนี y สำหรับสิ่งนี้ เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิกอีกครั้ง
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#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;
} ผลลัพธ์
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
