leetcode: 1695. Maximum Erasure Value

kldaji·2022년 6월 12일
0

leetcode

목록 보기
26/56

problem

Prefix sum with two pointers - 1

class Solution {
    fun maximumUniqueSubarray(nums: IntArray): Int {
        // calculate prefix sum
        val size = nums.size
        val prefixs = IntArray(size + 1) { 0 }
        for (i in 1..size) {
            prefixs[i] += prefixs[i - 1] + nums[i - 1]
        }
        
        val table = mutableMapOf<Int, Int>()
        var start = 0
        var answer = 0
        // find maximum unique sum of sub array
        nums.forEachIndexed { end, num ->
            // find duplicated value
            val temp = table[num]
            if (temp != null) {
                start = maxOf(start, temp + 1)                
            }
            // get sum of sub array
            answer = maxOf(answer, prefixs[end + 1] - prefixs[start])
            table[num] = end
        }
        return answer
    }
}

Prefix sum with two pointers - 2

class Solution {
    fun maximumUniqueSubarray(nums: IntArray): Int {        
        val table = mutableMapOf<Int, Int>()
        var left = 0
        var sum = 0
        var answer = 0
        // find maximum unique sum of sub array
        nums.forEachIndexed { right, num ->
            // find duplicated value
            val dupIndex = table[num]
            if (dupIndex != null) {
            	// subtract until duplicated index
                while (left <= dupIndex) {
                    sum -= nums[left++]
                }
            }
            // accumulate sum
            table[num] = right
            sum += num
            answer = maxOf(answer, sum)
        }
        return answer
    }
}

Hash set with two pointers

class Solution {
    fun maximumUniqueSubarray(nums: IntArray): Int {        
        val set = mutableSetOf<Int>()
        val size = nums.size
        var right = 0
        var left = 0
        var answer = 0
        var sum = 0
        while (right < size) {
            if (!set.contains(nums[right])) {
                set.add(nums[right])                
                sum += nums[right++]
                answer = maxOf(answer, sum)
            } else {
                set.remove(nums[left])
                sum -= nums[left++]
            }
        }
        return answer
    }
}
profile
다양한 관점에서 다양한 방법으로 문제 해결을 지향하는 안드로이드 개발자 입니다.

0개의 댓글