I am trying to implement version of Kadane's algorithm which returns subarray. Instead of just returning largest sum I would like to get container. Based on wiki pseudocode I have prepared simple implementation. However, I would like to avoid using indexes best_start and best_end. I can not find a way to fill out vector step by step using push_back.
Could you give me suggestion how should I change logic of this program?
std::vector<int> maxSubArrayWiki(const std::vector<int>& nums) {
std::vector<int> out;
int max_sum = INT_MIN;
int sum = 0;
int i = 0;
int current_start, best_start, best_end = 0;
for(const auto& n : nums){
if(sum <= 0) {
current_start = i;
out = {};
sum = n;
}
else {
sum += n;
}
if(sum > max_sum) {
max_sum = sum;
best_start = current_start;
out.push_back(n);
best_end = i + 1;
}
i++;
}
// is it possible to avoid following? return std::vector<int>(&nums[best_start], &nums[best_end]);
return out;
}
out:
4 2 1
expected:
4 -1 2 1
http://coliru.stacked-crooked.com/a/8d120f8f0ab923a6
Aucun commentaire:
Enregistrer un commentaire