LeetCode Entry

1695. Maximum Erasure Value

22.07.2025 medium 2025 kotlin rust

Max unique subarray sum window

1695. Maximum Erasure Value medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1057

Problem TLDR

Max unique subarray sum #medium #sliding_window

Intuition

Sliding window:

• expand every time
• shrink until condition

Approach

• use array for frequency map
• current index is irrelevant, just decrease the frequency

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

// 33ms
    fun maximumUniqueSubarray(n: IntArray): Int {
        val f = IntArray(10001); var j = 0; var s = 0
        return n.maxOf { x -> ++f[x]; s += x
            while (f[x] > 1) { s -= n[j]; --f[n[j++]] }; s
        }
    }

// 8ms
    fun maximumUniqueSubarray(n: IntArray): Int {
        val f = IntArray(10001); var j = 0; var r = 0; var s = 0
        for (x in n) {
            ++f[x]; s += x
            while (f[x] > 1) { s -= n[j]; --f[n[j++]] }
            r = max(r, s)
        }
        return r
    }

// 0ms
    pub fn maximum_unique_subarray(n: Vec<i32>) -> i32 {
        let (mut f, mut j, mut s) = ([0; 10001], 0, 0);
        n.iter().map(|&x| {
            f[x as usize] += 1; s += x;
            while f[x as usize] > 1 { s -= n[j]; f[n[j] as usize ] -= 1; j += 1 }; s
        }).max().unwrap()
    }

// 3ms
    int maximumUniqueSubarray(vector<int>& n) {
        int f[10001] = {}, j = 0, r = 0, s = 0;
        for (auto x: n) {
            ++f[x]; s += x;
            while (f[x] > 1) s -= n[j], --f[n[j++]];
            r = max(r, s);
        } return r;
    }