Question

How to find the max sum of a subarray of length k with unique elements (edge‑case‑safe) in C++

Answer 1

#include <iostream>
#include <vector>
#include <climits>
#include <unordered_map>

using std::vector;

std::pair<long long, vector<int>> findMaxUniqueSubarray(const vector<int>& nums, int k) {
    if (k <= 0 || k > (int)nums.size())
        return {0, {}};

    std::unordered_map<int,int> freq;
    long long sum = 0, bestSum = LLONG_MIN;
    int left = 0;
    vector<int> bestWindow;

    for (int right = 0; right < (int)nums.size(); right++) {
        freq[nums[right]]++;
        sum += nums[right];

        // shrink if duplicates appear
        while (freq[nums[right]] > 1) {
            freq[nums[left]]--;
            sum -= nums[left];
            left++;
        }

        // shrink if window too large
        while (right - left + 1 > k) {
            freq[nums[left]]--;
            sum -= nums[left];
            left++;
        }

        // valid window of size k
        if (right - left + 1 == k) {
            // IMPORTANT: choose the FIRST maximum window
            if (bestSum == LLONG_MIN) {
                bestSum = sum;
                bestWindow.assign(nums.begin() + left, nums.begin() + right + 1);
            }
        }
    }

    if (bestSum == LLONG_MIN) return {0, {}};
    return {bestSum, bestWindow};
}

int main() {
    vector<int> nums = {3, 2, 2, 4, 4, 6, 7, 7, 8, -1};
    int k = 3;

    auto result = findMaxUniqueSubarray(nums, k);

    std::cout << "Max sum = " << result.first << "\nElements: ";
    for (int x : result.second) std::cout << x << " ";
}



/* 
OUTPUT:

Max sum = 17
Elements: 4 6 7 

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>
#include <unordered_map>
#include <limits> // numeric_limits

/**
 * Finds the maximum sum of a subarray of length k containing only unique elements.
 * Returns a pair containing the max sum and the elements of that subarray.
 */
std::pair<long long, std::vector<int>> findMaxUniqueSubarray(const std::vector<int>& nums, int k) {
    if (k <= 0 || nums.size() < static_cast<size_t>(k)) {
        return {0, {}};
    }

    std::unordered_map<int, int> counts;
    long long current_sum = 0;
    long long max_sum = std::numeric_limits<long long>::min();
    int best_start_idx = -1;

    for (int i = 0; i < nums.size(); ++i) {
        // Add current element to window
        counts[nums[i]]++;
        current_sum += nums[i];

        // Remove element from the left if window exceeds k
        if (i >= k) {
            int left_val = nums[i - k];
            current_sum -= left_val;
            if (--counts[left_val] == 0) {
                counts.erase(left_val);
            }
        }

        // Check if window is valid (size k and all unique)
        if (i >= k - 1) {
            if (counts.size() == static_cast<size_t>(k)) {
                if (current_sum > max_sum) {
                    max_sum = current_sum;
                    best_start_idx = i - k + 1;
                }
            }
        }
    }

    // Prepare result
    if (best_start_idx == -1) return {0, {}}; // No valid subarray found
    
    std::vector<int> best_subarray(nums.begin() + best_start_idx, nums.begin() + best_start_idx + k);
    
    return {max_sum, best_subarray};
}

int main() {
    std::vector<int> data = {3, 2, 2, 4, 4, 6, 7, 7, 8, -1};
    int k = 3;

    auto [max_sum, elements] = findMaxUniqueSubarray(data, k);

    if (elements.empty()) {
        std::cout << "No valid subarray of length " << k << " with unique elements found." << std::endl;
    } else {
        std::cout << "Max Sum: " << max_sum << "\nElements: [ ";
        for (int x : elements) std::cout << x << " ";
        std::cout << "]" << std::endl;
    }

    return 0;
}



/* 
OUTPUT:

Max Sum: 17
Elements: [ 4 6 7 ]

*/

 

70+ SQL courses for beginners and professionals

Answer 3

#include <iostream>
#include <vector>
#include <climits>
#include <unordered_map>

std::pair<long long, std::vector<int>> findMaxUniqueSubarray(std::vector<int>& nums, int k) {
    long long max_sum = LLONG_MIN;
    int start = 0;
    std::unordered_map<int, int> umap;
    long long current_sum = 0;

    std::vector<int> best_subarray;

    for (int end = 0; end < nums.size(); end++) {
        current_sum += nums[end];
        umap[nums[end]]++;

        if (end - start + 1 == k) {
            if (umap.size() == k) {
                if (current_sum > max_sum) {
                    max_sum = current_sum;
                    best_subarray = std::vector<int>(nums.begin() + start, nums.begin() + end + 1);
                }
            }

            current_sum -= nums[start];
            umap[nums[start]]--;
            if (umap[nums[start]] == 0) {
                umap.erase(nums[start]);
            }
            start++;
        }
    }

    if (max_sum == LLONG_MIN) return {0, {}};
    return {max_sum, best_subarray};
}

int main() {
    std::vector<int> data = {3, 2, 2, 4, 4, 6, 7, 7, 8, -1};
    int k = 3;

    auto [max_sum, elements] = findMaxUniqueSubarray(data, k);

    if (elements.empty()) {
        std::cout << "No valid subarray of length " << k << " with unique elements found.\n";
    } else {
        std::cout << "Max Sum: " << max_sum << "\nElements: [ ";
        for (int x : elements) std::cout << x << " ";
        std::cout << "]\n";
    }
}



/* 
OUTPUT:

Max Sum: 17
Elements: [ 4 6 7 ]

*/

 

70+ SQL courses for beginners and professionals