Dynamic programming & explanation of the idea of divide and rule (taking leetcode question 53: finding the maximum subsequence as an example) (transferred from the explanation of leader liwei1419 in the comment area)

Write in front: this blog is only for my summary and notes, not for any commercial purpose. If there is any infringement, please contact me to delete it. Thank you. (see the end for reprint link)

Method 1: violent solution (understand, friends who are not interested can skip directly)

Enumerate all subintervals:

Use double-layer loop to enumerate all sub intervals;
Then sum all elements in the sub interval;
The time complexity is cubic.
Reference code 1:

Some boundary conditions should be noted here:

The variable i represents the subscript at the end;
The variable j indicates to go forward in sequence from subscript 0;

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                int sum = sumOfSubArray(nums, j, i);
                res = Math.max(res, sum);
            }
        }
        return res;
    }

    private int sumOfSubArray(int[] nums, int left, int right) {
        // Sum of subintervals
        int res = 0;
        for (int i = left; i <= right; i++) {
            res += nums[i];
        }
        return res;
    }

}

Complexity analysis:

Time complexity: O(N^3), where N is the length of the array;
Space complexity: O(1).
Timeout is found after submission. There are two situations:

"Dead cycle" is written in the program;
The code is "correct" and the complexity is high. This solution belongs to this case.
Optimization: in fact, the above code has some double counting. This is because the interval summation of the same prefix can be obtained by a method similar to "state transition".

For example, the sum of the calculated sub interval [1,4] can be obtained by adding num [4] to the calculated sub interval [1,3].

Therefore, we only need to enumerate the left endpoint of the sub order, and then scan the right endpoint, which can reduce the complexity by one level.

Reference code 2:

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = i; j < len; j++) {
                sum += nums[j];
                res = Math.max(res, sum);
            }
        }
        return res;
    }
}

Complexity analysis:

Time complexity: O(N^2)
Space complexity: O(1).
In fact, this problem is a very classic dynamic programming problem.

The problem was first proposed in 1977, but it was not until 1984 that Jay Kadane found the optimal solution of linear time.

Method 2: dynamic programming (classical dynamic programming problem)

Step 1: define status
Since a continuous subarray must end with a number, the state can be defined as follows:

dp[i]: represents the maximum sum of consecutive subarrays ending in nums[i].

A similar definition of state is: question 300 of "force buckle": "Longest ascending subsequence".

The definition of "what ends with what" is the application of the non aftereffect theory of dynamic programming. In short, to determine one thing, the classified discussion can be carried out, and whether a number is selected in the subsequence is the implicit condition of this problem.

Step 2: think about the state transition equation
According to the definition of state, since num [i] must be selected, and the continuous subsequence represented by dp[i] is one num [i] from the continuous subsequence represented by dp[i - 1] (possible).

Assuming that the array nums are all positive numbers, there must be dp[i] = dp[i - 1] + nums[i].

In general, dp[i - 1] may be negative. For example, the first few numbers are negative, and suddenly a positive number comes.

Therefore, classified discussion:

If dp[i - 1] > = 0, Num [i] can be directly connected to the array represented by dp[i - 1];
If dp[i - 1] < 0, then the number in front is getting smaller and smaller, so "start a new stove". A separate num [i] is dp[i].
The maximum value of the above two cases is the value of dp[i]. Write the following state transition equation:

dp[i] = dp[i - 1] + nums[i] , if  dp[i−1]≥0
        = nums[i]  ------------if dp[i−1]<0

It is recorded as "state transition equation 1".

The state transition equation can also be written in this way. Anyway, it is the maximum value, and there is no need to discuss it by classification. In these two cases, the maximum can be taken. Therefore, the state transition equation can also be written as follows:

dp[i] = max {nums[i], dp[i−1] + nums[i]}

It is recorded as "state transition equation 2".

The problems of dynamic programming often need to be discussed by classification, because the problems of dynamic programming have the characteristics of optimal substructure, that is, the optimal solution of large problems is usually obtained from the optimal solution of small problems, so we need to get what are the small problems of large problems through classified discussion.

Step 3: think about the initial value
dp[0] by definition must end with nums[0], so dp[0] = nums[0].

Step 4: think about output
The definition of status here is not the definition of the problem in the title. You cannot directly return the last status.

The output should read all dp[0], dp[1],..., dp[n - 1] and take the maximum value. The same applies to question 300 of "force buckle": "Longest ascending subsequence" . I often "stumble" in this step. Please pay attention.

Reference code 3: according to "state transition equation 1"

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i - 1] >= 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
        }

        // Finally, don't forget to look at it all for the maximum
        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }

}

Reference code 4: according to "state transition equation 2"

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int[] dp = new int[len];
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }

        int res = dp[0];
        for (int i = 1; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

Complexity analysis:
Time complexity: O(N)
Space complexity: O(N)
Step 5: think about optimizing space
Since the current state is only related to the previous state, we can reduce the spatial complexity to O(1).

Reference code 5:

public class Solution {

    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        // Called pre, it means the value of "previous state"
        int pre = nums[0];
        int res = pre;
        for (int i = 1; i < len; i++) {
            pre = Math.max(nums[i], pre + nums[i]);
            res = Math.max(res, pre);
        }
        return res;
    }

}

Complexity analysis:

Time complexity: O(N)
Space complexity: O(1)

Method 3: divide and conquer

The idea of divide and conquer is like this. In fact, it is also classified discussion.

The maximum sum of continuous subsequences is mainly obtained from the maximum sum of elements in these three molecular intervals:

Part 1: sub interval [left, mid];
Part 2: sub interval [mid + 1, right];
Part 3: sub intervals containing sub intervals [mid, mid + 1], i.e. num [mid] and num [mid + 1] must be selected.
The three parts can be maximized.

Note: when considering the continuous subarray spanning two intervals in part 3, since num [mid] and num [mid + 1] will be selected, they can spread from the middle to both sides to select the maximum value. For details, see "reference code 6".

Reference code 6:

public class Solution {

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

    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        // The element num [mid] must be included
        int sum = 0;
        int leftSum = Integer.MIN_VALUE;
        // The left half contains the num [mid] element. Where can I go at most
        // Go to the boundary and see what the maximum value is
        // Calculates the sum of the largest subarray ending in mid
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        int rightSum = Integer.MIN_VALUE;
        // The right half does not contain the num [mid] element. Where can I go at most
        // Calculates the sum of the largest subarray starting with mid+1
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }

    private int maxSubArraySum(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (left + right) >>> 1;
        return max3(maxSubArraySum(nums, left, mid),
                maxSubArraySum(nums, mid + 1, right),
                maxCrossingSum(nums, left, mid, right));
    }

    private int max3(int num1, int num2, int num3) {
        return Math.max(num1, Math.max(num2, num3));
    }
}

Complexity analysis:

Time complexity: O(N*logN). The depth of recursion here is logarithmic. Each layer needs to traverse the array (or half or quarter of the array);
Space complexity: O(logN). Constant variables are required to select the maximum value. The space required depends on the depth of the recursive stack.

reference material:
https://www.ge (remove Chinese characters and brackets to prevent harmony) eksforgeeks org/maximum-subarray-sum-using-divide-and-conquer-algorithm/

Author: Liwei 1419
Link: https://leetcode-cn.com/problems/maximum-subarray/solution/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

Tags: Java Algorithm leetcode Dynamic Programming

Posted by anna_cm on Mon, 09 May 2022 20:47:58 +0300