DevExCode

53. Maximum Subarray

ArrayDivide and ConquerDynamic Programming

Explanation:

  • Algorithmic Idea:

    • We can solve this problem using Kadane's algorithm, which is an efficient way to find the maximum subarray sum.
    • The main idea is to iterate through the array and keep track of the maximum subarray sum ending at each position.
    • At each index, we either include the current element in the sum or start a new subarray from the current element.
    • We update the maximum sum found so far by comparing it with the sum ending at the current index.

  • Step-by-Step Iterations:

    • For the input array [-2, 1, -3, 4, -1, 2, 1, -5, 4]:
      • Index 0: Current sum = -2, Max sum = -2
      • Index 1: Current sum = 1, Max sum = 1 (start a new subarray)
      • Index 2: Current sum = -2, Max sum = 1
      • Index 3: Current sum = 4, Max sum = 4 (start a new subarray)
      • Index 4: Current sum = 3, Max sum = 4
      • Index 5: Current sum = 5, Max sum = 5
      • Index 6: Current sum = 6, Max sum = 6
      • Index 7: Current sum = 1, Max sum = 6
      • Index 8: Current sum = 5, Max sum = 6

  • Time Complexity: O(n) - We iterate through the array once.

  • Space Complexity: O(1) - We use constant extra space for variables.

:

View Leetcode Problem
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int maxSum = nums[0];
        int currentSum = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question