Solution to problem 53 “Maximum Subarray” from LeetCode.

Problem Statement

Given an array nums of integers. Find a contiguous subarray (containing at least one element) whose sum of elements is maximum – and return that sum.

Example

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the maximum sum = 6.

Solution

Brute Force

If the array is empty, then the sum is zero.

If the array has one element – the value of that element is the maximum sum.

The idea is simple - create a variable to store the maximum sum value (initially assign the value of the first element).

Now we run the first loop from element 0 to the end of the array (iterator idx). Assign zero to the sum variable. This variable will store the value of the current sum. Run the second loop: from the current element to the end of the array (iterator jdx). Add the value nums[jdx] to the current sum sum. Compare the current sum with the maximum sum – if the current sum is greater, then assign the current sum value to the maximum.

Thus we calculate the sum of values of all possible subarrays.

func maxSubArray(nums []int) int {
    if len(nums)==0 {
        return 0
    }
    if len(nums)==1 {
        return nums[0]
    }
    maxsum:=nums[0]

    for idx:=0;idx<len(nums)-1;idx++ {
        sum:=0
        for jdx:=idx;jdx<len(nums)-1;jdx++ {
            sum += nums[jdx]
            if sum>maxsum{
                maxsum = sum
            }
        }
    }

    return maxsum
}

Greedy Algorithm

Greedy algorithm idea:

• go through the array
• compare the current element with the sum sum and the current element
• if the sum is greater, add the value of the current element to sum
• if the sum is less, assign the current element to sum
• compare sum and maxsum (if maxsum is less than sum - write the value of sum to maxsum)

func maxSubArray(nums []int) int {
    if len(nums)==0 {
        return 0
    }

    maxsum := nums[0]
    sum := nums[0]

    for idx:=1;idx<len(nums);idx++ {
        if nums[idx]> sum + nums[idx] {
            sum = nums[idx]
        } else {
            sum += nums[idx]
        }
        if sum>maxsum{
            maxsum = sum
        }
    }
    return maxsum
}