Maximum Subarray

ID: 35; easy

Maximum Subarray - LeetCodeLeetCode

Solution 1 (Go)

func maxSubArray(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    max, result := nums[0], 0
    for i := 0; i < len(nums); i++ {
        result += nums[i]
        // only update result when it can be increased
        if result > max {
            max = result
        }
        if result < 0 {
            result = 0
        }
    }
    return max
}

Solution 2 (Go)

func Max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

func maxSubArray(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    dp, result := make([]int, len(nums)), nums[0]
    // base case
    dp[0] = nums[0]
    // recursive relation
    for i := 1; i < len(nums); i++ {
        dp[i] = Max(dp[i-1] + nums[i], nums[i])
        result = Max(result, dp[i])
    }
    return result
}

Solution 3 (Java)

class Solution {
    public int maxSubArray(int[] nums) {
        int currSum = nums[0];
        int maxSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            // if currSum is reset to nums[i], it means that we start at nums[i] now
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }
}