DP solution & some thoughts


  • 306
    F

    Analysis of this problem:
    Apparently, this is a optimization problem, which can be usually solved by DP. So when it comes to DP, the first thing for us to figure out is the format of the sub problem(or the state of each sub problem). The format of the sub problem can be helpful when we are trying to come up with the recursive relation.

    At first, I think the sub problem should look like: maxSubArray(int A[], int i, int j), which means the maxSubArray for A[i: j]. In this way, our goal is to figure out what maxSubArray(A, 0, A.length - 1) is. However, if we define the format of the sub problem in this way, it's hard to find the connection from the sub problem to the original problem(at least for me). In other words, I can't find a way to divided the original problem into the sub problems and use the solutions of the sub problems to somehow create the solution of the original one.

    So I change the format of the sub problem into something like: maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element. Note that now the sub problem's format is less flexible and less powerful than the previous one because there's a limitation that A[i] should be contained in that sequence and we have to keep track of each solution of the sub problem to update the global optimal value. However, now the connect between the sub problem & the original one becomes clearer:

    maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i]; 
    

    And here's the code

    public int maxSubArray(int[] A) {
            int n = A.length;
            int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
            dp[0] = A[0];
            int max = dp[0];
            
            for(int i = 1; i < n; i++){
                dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
                max = Math.max(max, dp[i]);
            }
            
            return max;
    }

  • 3
    B

    very clear explanation!


  • 1
    M

    Thank for your share. That is very nice explanation.


  • 0
    J

    thank you so much!!!


  • 0

    very clear comment!!


  • 29
    L

    When we are talking about DP, the first problem comes out to our mind should be: what's the statement of the sub-problem, whose format should satisfy that if we've solved a sub-problem, it would be helpful for solving the next-step sub-problem, and, thus, eventually helpful for solving the original problem.

    Here is the sub-problem we state: denote int_local_max[i] as the max-sub-array-sum that ends with nums[i]. The relationship between the two steps is simple: int_local_max[i + 1] = max (int_local_max[i] + nums[i + 1], nums[i + 1]) or int_local_max[i + 1] = (int_local_max[i] > 0) ? int_local_max[i] + nums[i + 1] : nums[i + 1].

    Now, all we have to do is to scan through the array, and find which int_local_max[i] is the maximum of all the int_local_maxs.

    Here is the C++ version:

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if (nums.size() == 0) return 0;
            else if (nums.size() == 1) return nums.at(0);
            
            int int_local_max = nums.at(0), int_global_max = nums.at(0);
            size_t sz_length  = nums.size();
            for (size_t i = 1; i != sz_length; ++i) {
                int_local_max  = max(int_local_max + nums.at(i), nums.at(i));
                int_global_max = max(int_local_max, int_global_max);
            }
            
            return int_global_max;
        }
    };

  • 16
    L

    Actually, there is no need to record every dp[i].


  • 10
    X

    But I think this solution cannot handle all negative input.


  • 24

    There is no requirement that all input numbers should be positive. The following line:

    dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
    

    can also be written as:

    dp[i] = Math.max(A[i] + dp[i - 1] , A[i]);
    

  • 0
    J

    very good explanation.


  • 0

    @qkhhly it's not done because input numbers are required to be positive. What it means is that, a number is added only if increases the sum until now, i.e only if it's positive.


  • 41
    H

    My DP reasoning is as follows:

    To calculate sum(0,i), you have 2 choices: either adding sum(0,i-1) to a[i], or not. If sum(0,i-1) is negative, adding it to a[i] will only make a smaller sum, so we add only if it's non-negative.

    sum(0,i) = a[i] + (sum(0,i-1) < 0 ? 0 : sum(0,i-1))
    

    We can then use O(1) space to keep track of the max sum(0, i) so far.

    public int maxSubArray(int[] nums) {
    	if (nums == null || nums.length == 0) { return 0; }
    	int max = nums[0], sum = nums[0];
    	for (int i = 1; i < nums.length; i++) {
    		if (sum < 0) { sum = nums[i]; }
    		else {sum += nums[i]; }
    		max = Math.max(max, sum);
    	}
    	return max;
    }
    

  • 3
    D

    brilliant. you changed the way I see dynamic programming problems.


  • 0
    R
    This post is deleted!

  • 0
    R

    no need of line

    if (nums == null || nums.length == 0) { return 0; }
    

    since it is given that array is containing at least one number.


  • 6
    A

    lovely explanation, but if you observe carefully, you don't need O(n) space, all you are using is dp[i - 1]. You can easily update the solution using O(1) space.


  • 0
    L

    O(1) space O(n)time

    public class Solution {
    public int maxSubArray(int[] nums) {
    int sum = Integer.MIN_VALUE;
    int max = Integer.MIN_VALUE;
    for(int num : nums){
    if(sum < 0){
    sum = num;
    max = Math.max(max, sum);
    }
    else if(num < 0){
    max = Math.max(max, sum);
    sum += num;
    } else {
    sum += num;
    max = Math.max(max, sum);
    }
    }
    return max;
    }
    }


  • 1
    Z

    clear explanation of DP


  • 1
    0

    @Xulai_Cao I tried it. All negtive still works. The dp contain all A[i], and the max save the smallest A[i]. so it works


  • 0
    S

    excellent!!!!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.