Sum of Array the Maximum Consecutive Subarray

In the past few weeks, I have been learning a lot of algorithms and data structures. Finding Kotlin written algorithms has proven challenging. So let us fix that by with writing our own. if you can't beat them, look for a way to beat them 😅.

The problem.

Given an array of integers, find the maximum possible sum you can get from one of its contiguous subarrays. The subarray from which this sum comes must contain at least 1 element.

One of the methods to solve this will be through using a nested for loop, the first will loop through all the elements and calculating the sum and saving it to a variable var max_sum. This solution would be correct although it would not be efficient as it runs at 0(n²).

There are many dynamic algorithms that can be used to make this program efficient by running linearly. In this instance, we will use the popular Kadane's Algorithm.

We will create a method ArrayMaxConsecutiveSum which takes in a parameter inputArray: IntArray. Then a variable max_sum which will be equal to the first element of the array var max_sum = inputArray[0], variable current_sum which will be equal to our maximum sum, var current_sum = max_sum, a for loop, given the size of the array we will make the current_sum equal to the result of the element input position of the array plus the current_sumcompared to the next element input position. Update the max_sum with the current_sum.

To make it work we will return the max_sum.

Now that wasn't hard 😄 😄.

Let's look at the code

fun ArrayMaxConsecutiveSum (inputArray: IntArray): Int {

    var max_sum = inputArray[0]
    var current_sum = max_sum

    for (i in inputArray.indices) {
        current_sum = (inputArray[i] + current_sum).coerceAtLeast(inputArray[i]) 
/**
* checks what is greater the current_sum
  plus the next element input position or
  the next element input position alone
 **/
        max_sum = current_sum.coerceAtLeast(max_sum) // we update the max sum with the current sum if it's greater
    }

    return max_sum
}

Github Repo

Thank you for reading, please share if you found it helpful 💯.

Asante Sana

Comments

[Brian]

For Python Engineers

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

def max_sub_array(nums):
    if len(nums) == 1:
        return nums[0]

    total = nums[0]
    best = nums[0]

    for i in nums[1:]:
        if i > (total + i):
            total = i
        else:
            total += i

        best = max(best, total)

    return best