समस्या विवरण
मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक मान k है, हमें k नॉन-ओवरलैपिंग, नॉन-खाली सबलिस्ट्स ढूंढने हैं जैसे कि उनके योग का योग अधिकतम हो। हम मान सकते हैं कि k, nums के आकार से कम या बराबर है।
उदाहरण के लिए, यदि इनपुट है nums = [11, -1, 2, 1, 6, -24, 11, -9, 6] k = 3, तो आउटपुट 36 होगा, क्योंकि हम सबलिस्ट्स [11, -1, 2, 1, 6], [11], और [6] चुन सकते हैं जिससे योग [19, 11, 6] = 36 मिलता है।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम डायनामिक प्रोग्रामिंग का उपयोग करेंगे:
- n := nums का आकार
- यदि n == 0 या k == 0, तो 0 वापस करें
- आकार k+1 का एक ऐरे hi परिभाषित करें और -अनंत से भरें
- आकार k+1 का एक और ऐरे open परिभाषित करें और -अनंत से भरें
- hi[0] := 0
- nums में प्रत्येक num के लिए:
- आकार k+1 का एक ऐरे nopen परिभाषित करें और -अनंत से भरें
- i := 1 से k तक:
- यदि open[i] > -अनंत, तो nopen[i] := open[i] + num
- यदि hi[i-1] > -अनंत, तो nopen[i] := max(nopen[i], hi[i-1] + num)
- open := move(nopen)
- i := 1 से k तक: hi[i] := max(hi[i], open[i])
- hi[k] वापस करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0 || k == 0) return 0;
vector<int> hi(k + 1, INT_MIN), open(k + 1, INT_MIN);
hi[0] = 0;
for (int num : nums) {
vector<int> nopen(k + 1, INT_MIN);
for (int i = 1; i <= k; ++i) {
if (open[i] > INT_MIN)
nopen[i] = open[i] + num;
if (hi[i - 1] > INT_MIN)
nopen[i] = max(nopen[i], hi[i - 1] + num);
}
open = move(nopen);
for (int i = 1; i <= k; ++i)
hi[i] = max(hi[i], open[i]);
}
return hi[k];
}
int main() {
vector<int> v = {11, -1, 2, 1, 6, -24, 11, -9, 6};
int k = 3;
cout << solve(v, 3);
}
इनपुट
{11, -1, 2, 1, 6, -24, 11, -9, 6}, 3
आउटपुट
36