text: # 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
explanation: The document provides an overview of different solutions to the LeetCode problem "Maximum Subarray," including brute force, a method based on negative values, dynamic programming (DP), and divide and conquer. It describes the problem, provides an example, and explains the time and space complexities of each solution. The document does not contain a specific question or a question and answer.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # 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
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document provides an overview of different solutions to the LeetCode problem "Maximum Subarray," including brute force, a method based on negative values, dynamic programming (DP), and divide and conquer. It describes the problem, provides an example, and explains the time and space complexities of each solution. The document does not contain a specific question or a question and answer.
  
  Label: no-question