Home » leet code » Leetcode 53. Maximum Subarray (Medium)

Leetcode 53. Maximum Subarray (Medium)

Leave a Comment / By /

LeetCode 53. Maximum Subarray :Hey there, coding enthusiasts! Welcome back to another exciting coding session. Today’s problem is a treat—literally! We’re going to solve the “Maximum Subarray” or “LeetCode 53. ‘

There are various approach to solve “Maximum Subarray” problem . we discuss three main approach which are optimaized – Kedane algo , Dp , Divide and conquer and excluded the bruteforce approach which cost about O(n^2).

Kedane Approach : Leetcode 53 – Maxium Subarray

Time Complexity : O(n)

1: Initialize Variables

  • Create two variables, max_sum and current_sum, both initially set to the first element of the array.

2: Traverse the Array

  • Loop through the array from the second element to the end.

3: Update current_sum

  • At each step, update current_sum by choosing the maximum of the current element and the current element added to current_sum.

4: Update max_sum

  • Update max_sum by selecting the maximum of the current max_sum and the current_sum.

5: Repeat and Finish

  • Continue these steps until you’ve traversed the entire array.

6: Enjoy the Maximum Subarray Sum

  • Once you’ve finished the loop, the value of max_sum will hold the answer you seek

To get you started, let’s illustrate how Kadane’s Algorithm works with an example:

Example:

Let’s take the array [-2, 1, -3, 4, -1, 2, 1, -5, 4]. We’ll step through it and update our maximum subarray sum as we go:

able:

Iterationi ValueCurrent Elementsummaxiif Condition (Sum Value)
10-2-2-20
21111–
32-3-210
43444–
54-134–
65255–
76166–
87-5160
98456–
Dry and Run of Maxium Subarray Kedne Appraoch

In the end, the maximum subarray sum is 6, which corresponds to the subarray [4, -1, 2, 1].

Codes : Kedane Appraoch Leetcode max subarray

C++ Kedane Appraoch Leetcode Maxium Subaray

#include <iostream>
#include <vector>

class Solution {
public:
    int maxSubArray(vector<int>& arr) {
        int sum = 0;
        int maxi = arr[0];
        for (int i = 0; i < arr.size(); i++) {
            sum = sum + arr[i];
            maxi = std::max(maxi, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxi;
    }
};

Java Kedane Appraoch Leet Code 53

public class Solution {
    public int maxSubArray(int[] arr) {
        int sum = 0;
        int maxi = arr[0];
        for (int i = 0; i < arr.length; i++) {
            sum = sum + arr[i];
            maxi = Math.max(maxi, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxi;
    }
}

Python Kedane Appraoch Leetcode subarray

class Solution:
    def maxSubArray(self, arr):
        sum = 0
        maxi = arr[0]
        for i in range(len(arr)):
            sum = sum + arr[i]
            maxi = max(maxi, sum)
            if sum < 0:
                sum = 0
        return maxi

JavaScript Kedane Appraoch Leet Code 53

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    
        let sum = 0;
        let maxi = nums[0];
        for (let i = 0; i < nums.length; i++) {
            sum = sum + nums[i];
            maxi = Math.max(maxi, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return maxi;

};

Dyanamic Programing approach – Leetcode Subarray 53

Time complexity : O(n)

  1. Initialization: The code initializes two variables, max_sum and max_ending_here, both set to the first element of the input array, nums.
  2. Looping Through the Array: It then iterates through the input array, starting from the second element.
  3. Dynamic Programming: For each element, it employs a dynamic programming approach. max_ending_here keeps track of the maximum sum ending at the current position, considering whether to extend the subarray or start a new one.
  4. Updating Maximum: max_sum is updated with the maximum between its current value and max_ending_here. This ensures we always have the overall maximum sum seen so far.
  5. Result: After the loop, the function returns the max_sum, which represents the maximum subarray sum found in the input array.

Dry and Run

Imagine we have the array: [−2, 1, −3, 4, −1, 2, 1, −5, 4]. We need to find the contiguous subarray with the largest sum. To start, we’ll create a table to keep track of our progress:

Index012345678
Array Value-21-34-121-54

Now, we’ll create another table to record the maximum subarray sum ending at each index:

Index012345678
Max Sum-21-2435615

We can see that our final answer is 6, which corresponds to the subarray [4, -1, 2, 1].

Codes : DP Appraoch :

Certainly! Here’s the maxSubArray solution in C++, Java, Python, and JavaScript, each with an H3 heading for clarity.

C++ Solution

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum = nums[0];      
        int max_ending_here = nums[0]; 

        for (int i = 1; i < nums.size(); i++) {
            max_ending_here = std::max(max_ending_here + nums[i], nums[i]);
            max_sum = std::max(max_sum, max_ending_here);
        }

        return max_sum;
    }
};

Java Solution

public class Solution {
    public int maxSubArray(int[] nums) {
        int max_sum = nums[0];      
        int max_ending_here = nums[0]; 

        for (int i = 1; i < nums.length; i++) {
            max_ending_here = Math.max(max_ending_here + nums[i], nums[i]);
            max_sum = Math.max(max_sum, max_ending_here);
        }

        return max_sum;
    }
}

Python Solution

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = max_ending_here = nums[0]

        for i in range(1, len(nums)):
            max_ending_here = max(max_ending_here + nums[i], nums[i])
            max_sum = max(max_sum, max_ending_here)

        return max_sum

JavaScript Solution

var maxSubArray = function(nums) {
    let max_sum = nums[0];
    let max_ending_here = nums[0];

    for (let i = 1; i < nums.length; i++) {
        max_ending_here = Math.max(max_ending_here + nums[i], nums[i]);
        max_sum = Math.max(max_sum, max_ending_here);
    }

    return max_sum;
};

Divide and Conquer approach – Leetcode Subarray 53

Time Complexity : O(n log n)

Now, let’s see how this technique works for Leetcode 53. Here’s the high-level idea:

  1. Divide: We split the given array into two halves, creating left and right subarrays.
  2. Conquer: We find the maximum subarray in the left and right subarrays. This step involves recursion.
  3. Combine: We combine the results from the left and right subarrays to find the maximum subarray that spans both halves.

By applying this method recursively, we’ll eventually find the maximum subarray for the entire input array.

Codes : Divide and Conquer Approach

Certainly! The provided code is an implementation of the “maximum subarray sum” problem using the divide and conquer approach. Here’s the code in C++, Java, Python, and JavaScript:

C++: Divide and conquer approach leet code 53

#include <vector>
#include <climits>

class Solution {
public:
    int maxCrossingSubarray(std::vector<int>& nums, int low, int mid, int high) {
        int left_sum = INT_MIN;
        int sum = 0;
        for (int i = mid; i >= low; i--) {
            sum += nums[i];
            if (sum > left_sum) {
                left_sum = sum;
            }
        }

        int right_sum = INT_MIN;
        sum = 0;
        for (int i = mid + 1; i <= high; i++) {
            sum += nums[i];
            if (sum > right_sum) {
                right_sum = sum;
            }
        }

        return left_sum + right_sum;
    }

    int maxSubArrayHelper(std::vector<int>& nums, int low, int high) {
        if (low == high) {
            return nums[low];
        }

        int mid = (low + high) / 2;

        int left_max = maxSubArrayHelper(nums, low, mid);
        int right_max = maxSubArrayHelper(nums, mid + 1, high);
        int cross_max = maxCrossingSubarray(nums, low, mid, high);

        return std::max({left_max, right_max, cross_max});
    }

    int maxSubArray(std::vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        return maxSubArrayHelper(nums, 0, nums.size() - 1);
    }
};

Java: Divide and conquer approach Max Subarray

import java.util.*;

class Solution {
    public int maxCrossingSubarray(int[] nums, int low, int mid, int high) {
        int left_sum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= low; i--) {
            sum += nums[i];
            if (sum > left_sum) {
                left_sum = sum;
            }
        }

        int right_sum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= high; i++) {
            sum += nums[i];
            if (sum > right_sum) {
                right_sum = sum;
            }
        }

        return left_sum + right_sum;
    }

    public int maxSubArrayHelper(int[] nums, int low, int high) {
        if (low == high) {
            return nums[low];
        }

        int mid = (low + high) / 2;

        int left_max = maxSubArrayHelper(nums, low, mid);
        int right_max = maxSubArrayHelper(nums, mid + 1, high);
        int cross_max = maxCrossingSubarray(nums, low, mid, high);

        return Math.max(Math.max(left_max, right_max), cross_max);
    }

    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        return maxSubArrayHelper(nums, 0, nums.length - 1);
    }
}

Python: Divide and conquer approach leetcode 53

class Solution:
    def maxCrossingSubarray(self, nums, low, mid, high):
        left_sum = float('-inf')
        sum = 0
        for i in range(mid, low - 1, -1):
            sum += nums[i]
            if sum > left_sum:
                left_sum = sum

        right_sum = float('-inf')
        sum = 0
        for i in range(mid + 1, high + 1):
            sum += nums[i]
            if sum > right_sum:
                right_sum = sum

        return left_sum + right_sum

    def maxSubArrayHelper(self, nums, low, high):
        if low == high:
            return nums[low]

        mid = (low + high) // 2

        left_max = self.maxSubArrayHelper(nums, low, mid)
        right_max = self.maxSubArrayHelper(nums, mid + 1, high)
        cross_max = self.maxCrossingSubarray(nums, low, mid, high)

        return max(left_max, right_max, cross_max)

    def maxSubArray(self, nums):
        if not nums:
            return 0
        return self.maxSubArrayHelper(nums, 0, len(nums) - 1)

Now, go ahead and try solving the “LeetCode 53 Maximum Subarray” problem yourself. You’ve got this! 🚴‍♂️🔍

List of Some important Leet code Questions:

Leave a Reply