Trong bài toán, chúng ta có n mảng có độ dài khác nhau. Nhiệm vụ của chúng ta là Tìm mảng tổng lớn nhất có độ dài nhỏ hơn hoặc bằng m.
Chúng ta cần tìm mảng con từ mảng để tổng lớn nhất và làm cho độ dài của tất cả các mảng con cộng lại bằng m.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
n =3, m =4arrOfArr [] [] ={{5, 2, -1, 4, -3} {3, -2, 1, 6} {-2, 0, 5}} Đầu ra
20
Giải thích
SubArrays là {5, 4}, {6}, {5}, length =2 + 1 + 1 =4Sum =5 + 4 + 6 + 5 =20 Phương pháp tiếp cận giải pháp
Vấn đề có thể được giải quyết bằng cách sử dụng phương pháp lập trình động. Chúng ta sẽ tạo một mảng DP và tính tổng mảng tích lũy có độ dài k thay đổi từ 0 đến m.
Trong mảng DP, lưu trữ tổng mảng tối đa cho tất cả các độ dài từ 0 đến m trước mỗi mảng trong DP 2D. Sau đó, trả về tổng lớn nhất sẽ nằm ở hàng cuối cùng của mảng.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include using namespace std; #define N 5int findMax (int a, int b) {if (a> b) return a; return b;} int findMaxSumArray (int arr [] [N], int M) {int DP [N] [M]; int sumArray [M]; int sum [M]; memset (DP, -1, sizeof (DP [0] [0]) * N * M); sumArray [0] =0; DP [0] [0] =0; for (int i =1; i <=5; i ++) {int len =arr [i - 1] [0]; for (int j =1; j <=len; j ++) {sumArray [j] =arr [i - 1] [j]; sumArray [j] + =sumArray [j - 1]; tổng [j] =-100; } for (int j =1; j <=len &&j <=6; j ++) for (int k =1; k <=len; k ++) if (j + k - 1 <=len) sum [j] =findMax (sum [j], sumArray [j + k - 1] - sumArray [k - 1]); for (int j =0; j <=6; j ++) DP [i] [j] =DP [i - 1] [j]; for (int j =1; j <=6; j ++) for (int cur =1; cur <=j &&cur <=len; cur ++) DP [i] [j] =findMax (DP [i] [j] , DP [i - 1] [j - cur] + sum [cur]); } int maxSum =0; for (int i =0; i <=6; i ++) maxSum =findMax (maxSum, DP [5] [i]); return maxSum;} int main () {int arr [] [N] ={{3, 2, -1, 6}, {2, 7, -1}, {3, 2, 2, -4}}; int m =4; cout <<"Mảng tổng tối đa có độ dài nhỏ hơn hoặc bằng" < Đầu ra
Mảng tổng tối đa có độ dài nhỏ hơn hoặc bằng 4:15