Maximum Product Subarray problem in Kotlin | Kadane’s algorithm

by

The Maximum Product Subarray problem is a classic problem in computer science that involves finding the maximum product that can be obtained from any contiguous subarray of an input array of numbers. Given an array of n integers, the problem is to find the subarray that has the maximum product of its elements.

For example, given the input array [2, 3, -2, 4], the maximum product subarray is [2, 3], and the maximum product is 6, which is the product of 2 and 3. Another example is the input array [-2, 0, -1], which has a maximum product of 0, obtained by taking an empty subarray.

Solving the Maximum Product Subarray problem can be done using various algorithms, including Kadane’s algorithm, which is a modified version of the Kadane’s algorithm for the Maximum Sum Subarray problem. The time complexity of most algorithms for this problem is O(n), where n is the size of the input array. This problem has applications in many areas, including finance, image processing, and signal processing.

Kotlin
fun maxProduct(nums: IntArray): Int {
    var maxSoFar = nums[0]
    var minSoFar = nums[0]
    var maxProduct = nums[0]
    
    for (i in 1 until nums.size) {
        val tempMax = maxSoFar
        maxSoFar = maxOf(nums[i], maxOf(nums[i] * maxSoFar, nums[i] * minSoFar))
        minSoFar = minOf(nums[i], minOf(nums[i] * tempMax, nums[i] * minSoFar))
        maxProduct = maxOf(maxProduct, maxSoFar)
    }
    
    return maxProduct
}

This function takes an integer array nums as input, where each element represents a number. The goal is to find the maximum product of any subarray of nums. The algorithm works by iterating over the array from left to right and keeping track of the maximum product seen so far, as well as the maximum and minimum product that can be obtained by including the current element.

At each step, we update the maximum and minimum product seen so far based on whether the current element is positive or negative. If the current element is positive, the maximum product can be obtained by either including the current element or by multiplying it with the maximum product seen so far. Similarly, the minimum product can be obtained by either including the current element or by multiplying it with the minimum product seen so far. If the current element is negative, we swap the roles of the maximum and minimum products. Finally, we return the maximum product seen so far.

Kotlin
fun maxProduct(nums: IntArray): Int {
    var maxSoFar = nums[0]
    var minSoFar = nums[0]
    var maxProduct = nums[0]
    
    for (i in 1 until nums.size) {
        val tempMax = maxSoFar
        maxSoFar = maxOf(nums[i], maxOf(nums[i] * maxSoFar, nums[i] * minSoFar))
        minSoFar = minOf(nums[i], minOf(nums[i] * tempMax, nums[i] * minSoFar))
        maxProduct = maxOf(maxProduct, maxSoFar)
    }
    
    return maxProduct
}
fun main(){
    val nums = intArrayOf(2, 3, -2, 4)
	val maxProduct = maxProduct(nums)
	println(maxProduct) // Output: 6

}

In this example, the input array nums represents the numbers [2, 3, -2, 4], and the output is 6, which represents the maximum product of any subarray of nums. The maximum product is obtained by multiplying the elements at indices 0 and 1: 2 * 3 = 6.

Leave a Comment