Largest Subset Sum Problem

by

Problem Explanation: You are given an array of integers. Your task is to find the largest possible sum of a subset of the given array, such that no two elements in the subset are adjacent to each other.

Example:

Input: [2, 5, 3, 1, 7, 9, 10]

Output: 22 (Subset: 2, 3, 7, 10)

Expected Time and Space Complexity: O(n) time complexity and O(1) space complexity.

Constraints:

  • The input array contains at most 10^6 elements.
  • Each element of the array is between -10^9 and 10^9.

Kotlin Solution:

Kotlin
fun largestSubsetSum(arr: IntArray): Int {
    var incl = arr[0] // maximum sum including the previous element
    var excl = 0 // maximum sum excluding the previous element
    var temp: Int

    for (i in 1 until arr.size) {
        temp = maxOf(incl, excl)
        incl = excl + arr[i]
        excl = temp
    }
    return maxOf(incl, excl)
}

fun main() {
    val arr = intArrayOf(2, 5, 3, 1, 7, 9, 10)
    val result = largestSubsetSum(arr)
    println("Largest Subset Sum: $result")
}

Leave a Comment