# LeetCode Maximum Subarray: 4 methods, DP, Divide and Conquer

## Overview

I summarize different solutions to the LeetCode problem Maximum Subarray including DP, Divide and Conquer, there are 4 different approaches as far as I know.

## Problem Definition

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array `[−2,1,−3,4,−1,2,1,−5,4]`,
the contiguous subarray `[4,−1,2,1]` has the largest sum = `6`.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

## Solutions and Analysis

(1) Brute Force: for every possible contiguous subarray A[i…j] we get the sum and return the maximum one among them. Since we can obtain the sum in constant time (why?), the time complexity would be O(N^2) while the space complexity would be O(1).

(2) Negative value cannot be border: This method is based on such a fact that the negative value cannot be the border element in the maximum subarray, since you remove the negative border out, the sum obviously get larger. So we can scan the array from left to right and keep a current sum over the scanned elements. If the current sum become negative, we set it as zero, if the sum is larger than the global maximum sum, we update the maximum sum. To some extent, this is also could be interpreted as DP approach. The following is the code:

(3) DP: Let S[j] denote the maximum sum value among all those subarrays ended at A[j], we have the recursive definition: S[j] = max(A[j], A[j] + S[j - 1]).

(4) Divide and Conquer: divide the array into left and right part, recursively find the maximum sub array in the left and right parts. The third candidate is the subarray cross the mid element (could be calculated in linear time). Then we compare these three result, return the maximum one. The time is T(N) = 2*T(N/2) + O(N), by master’s theroy the time complexity is O(NlogN).

## Summary

Different solutions are summarized to solve the LeetCode problem Maximum Subarray including DP, Divide and Conquer, I gave analysis about 4 methods to my knowledge.

Written on May 20, 2013
The text passage provides an overview of the LeetCode problem "Maximum Subarray" and discusses four different methods to solve it, including brute force, a method based on negative values, dynamic programming (DP), and divide and conquer. It also includes a problem definition with an example.
no_question

the passage does not contain a mathematical question that requires an answer. instead, it describes a problem and provides multiple methods to solve it, along with their time and space complexities.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# LeetCode Maximum Subarray: 4 methods, DP, Divide and Conquer

## Overview

I summarize different solutions to the LeetCode problem Maximum Subarray including DP, Divide and Conquer, there are 4 different approaches as far as I know.

## Problem Definition

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array `[−2,1,−3,4,−1,2,1,−5,4]`,
the contiguous subarray `[4,−1,2,1]` has the largest sum = `6`.

More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

## Solutions and Analysis

(1) Brute Force: for every possible contiguous subarray A[i…j] we get the sum and return the maximum one among them. Since we can obtain the sum in constant time (why?), the time complexity would be O(N^2) while the space complexity would be O(1).

(2) Negative value cannot be border: This method is based on such a fact that the negative value cannot be the border element in the maximum subarray, since you remove the negative border out, the sum obviously get larger. So we can scan the array from left to right and keep a current sum over the scanned elements. If the current sum become negative, we set it as zero, if the sum is larger than the global maximum sum, we update the maximum sum. To some extent, this is also could be interpreted as DP approach. The following is the code:

(3) DP: Let S[j] denote the maximum sum value among all those subarrays ended at A[j], we have the recursive definition: S[j] = max(A[j], A[j] + S[j - 1]).

(4) Divide and Conquer: divide the array into left and right part, recursively find the maximum sub array in the left and right parts. The third candidate is the subarray cross the mid element (could be calculated in linear time). Then we compare these three result, return the maximum one. The time is T(N) = 2*T(N/2) + O(N), by master’s theroy the time complexity is O(NlogN).

## Summary

Different solutions are summarized to solve the LeetCode problem Maximum Subarray including DP, Divide and Conquer, I gave analysis about 4 methods to my knowledge.

Written on May 20, 2013
user
The text passage provides an overview of the LeetCode problem "Maximum Subarray" and discusses four different methods to solve it, including brute force, a method based on negative values, dynamic programming (DP), and divide and conquer. It also includes a problem definition with an example.

TYPE: NO_QUESTION

The passage does not contain a mathematical question that requires an answer. Instead, it describes a problem and provides multiple methods to solve it, along with their time and space complexities.