mercredi 28 juillet 2021

Maximum subarray - returning container

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