Why does greedy not work here?
I'm trying to solve https://leetcode.com/problems/maximum-subsequence-score My algorithm greedily chooses the best choice until we reach k But some large 1000 number test case is failing. I'm not able to understand. AI couldn't help me come up with a smaller case that fails class Solution { public: long long maxScore(vector& nums1, vector& nums2, int k) { unordered_set selectedIndices = {}; long long selectedSum = 0; long long selectedProd = LONG_MAX; for (long long i = 0; i < k; i++) { long long newSum = 0; long long newProd = LONG_MIN; long long newIndex = 0; long long currentMaxProd = LONG_MIN; for (long long j = 0; j < nums2.size(); j++) { if (selectedIndices.find(j) != selectedIndices.end()) { continue; } long long updatedProd = (selectedSum + (long long) nums1[j]) * min(selectedProd, (long long) nums2[j]); if(updatedProd > currentMaxProd) { currentMaxProd = updatedProd; newIndex = j; newSum = nums1[j]; newProd = min(selectedProd, (long long) nums2[j]); } } selectedSum += newSum; selectedProd = newProd; cout
I'm trying to solve https://leetcode.com/problems/maximum-subsequence-score
My algorithm greedily chooses the best choice until we reach k
But some large 1000 number test case is failing. I'm not able to understand. AI couldn't help me come up with a smaller case that fails
class Solution {
public:
long long maxScore(vector& nums1, vector& nums2, int k) {
unordered_set selectedIndices = {};
long long selectedSum = 0;
long long selectedProd = LONG_MAX;
for (long long i = 0; i < k; i++) {
long long newSum = 0;
long long newProd = LONG_MIN;
long long newIndex = 0;
long long currentMaxProd = LONG_MIN;
for (long long j = 0; j < nums2.size(); j++) {
if (selectedIndices.find(j) != selectedIndices.end()) {
continue;
}
long long updatedProd = (selectedSum + (long long) nums1[j]) * min(selectedProd, (long long) nums2[j]);
if(updatedProd > currentMaxProd) {
currentMaxProd = updatedProd;
newIndex = j;
newSum = nums1[j];
newProd = min(selectedProd, (long long) nums2[j]);
}
}
selectedSum += newSum;
selectedProd = newProd;
cout << " Selecting " << newSum << " " << selectedProd << endl;
selectedIndices.insert(newIndex);
}
cout << "count: " << selectedIndices.size() << " " << selectedSum << " " << selectedProd << endl;
return selectedSum * selectedProd;
}
};