[interview high frequency questions] sequential DP questions with difficulty of 3/5 and direct construction

Title Description

This is a LeetCode Upper 「1537. Maximum score 」 , The difficulty is 「 difficult 」.

Tag : 「 The prefix and 」、「 structure 」、「 Double pointer 」、「 Sequence DP」、「 Dynamic programming 」

You have two Orderly   And the elements in the array are different from each other  nums1 and  nums2 .

One   Legal path   The definition is as follows ：

• Select array nums1 perhaps nums2 To traverse the （ From the subscript Start at ）.
• Traverses the current array from left to right .
• If you meet nums1  and nums2  Values that exist in , Then you can switch the path to another array corresponding to the number and continue to traverse （ But in a legal path, duplicate numbers are counted only once ）.

Scores and numbers are defined as different paths .

Please return the maximum score of all possible legal paths .

Because the answer can be big , Please put it on Take the rest and return .

Example 1：

 Input ：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]

 Output ：30

 explain ： The legal path includes ：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（ from  nums1  To traverse the ）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  （ from  nums2  To traverse the ）
 The maximum score is the green path in the figure above  [2,4,6,8,10] .

Example 2：

 Input ：nums1 = [1,3,5,7,9], nums2 = [3,5,100]

 Output ：109

 explain ： The maximum score is from the path  [1,3,5,100]  obtain .

Example 3：

 Input ：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]

 Output ：40

 explain ：nums1  and  nums2  There is no same number between .
 The maximum score is from the path  [6,7,8,9,10]  obtain .

Example 4：

 Input ：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]

 Output ：61

Tips ：

• nums1 and   nums2  Are strictly incremented arrays .

The prefix and + structure （ Piecewise calculation ）

A simple and correct approach , We construct a decision scheme , So that the maximum score can be calculated directly .

First , In the best path, all common points must pass through , So we can merge points with equal values , That is to say, it is regarded as the same point .

Use both arrays to satisfy 「 Monotone increasing 」, We can go through The common points are calculated according to the complexity of , In binary Stored in the form of list Array （ The meaning of two tuples is ）.

about list Each pair of adjacent elements in （ Adjacent common point ）, Assuming that and , We can go through 「 The prefix and 」 To calculate the as well as And , Thus the decision is made in （ Or rather, , These two are the same point ） when , Which section should we go .

When the scores between all common points are calculated , For the first two ends of the best route , It's also a combination 「 The prefix and 」 Do the same logic processing .

Code ：

class Solution {
    int MOD = (int)1e9 + 7;
    public int maxSum(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        long[] s1 = new long[n + 10], s2 = new long[m + 10];
        for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + nums1[i - 1];
        for (int i = 1; i <= m; i++) s2[i] = s2[i - 1] + nums2[i - 1];
        List<int[]> list = new ArrayList<>();
        for (int i = 0, j = 0; i < n && j < m; ) {
            if (nums1[i] == nums2[j]) list.add(new int[]{i, j});
            if (nums1[i] < nums2[j]) i++;
            else j++;
        }
        long ans = 0;
        for (int i = 0, p1 = -1, p2 = -1; i <= list.size(); i++) {
            int idx1 = 0, idx2 = 0;
            if (i < list.size()) {
                int[] info = list.get(i);
                idx1 = info[0]; idx2 = info[1];
            } else {
                idx1 = n - 1; idx2 = m - 1;
            }
            long t1 = s1[idx1 + 1] - s1[p1 + 1], t2 = s2[idx2 + 1] - s2[p2 + 1];
            ans += Math.max(t1, t2);
            p1 = idx1; p2 = idx2;
        }
        return (int)(ans % MOD);
    }
}

• Time complexity ：
• Spatial complexity ：

Sequence DP

Another common practice is 「 Sequence DP」 practice .

Definition On behalf of the nums1 Move on , arrive My biggest score ; Definition On behalf of the nums2 Move on , arrive My biggest score .

Because the analysis of the two is similar , We use For example .

Without losing general considerations How to transfer , Suppose the current processing is , according to Whether it is a public point , Discuss the situation by situation ：

• Not for public use , At this time, only Transfer from , That is to say ;
• For the public point （ Hypothesis and public ）, At this point, you can start from or Transfer from , We need to take and The maximum of , That is to say .

what's more , We need to make sure that the calculations when , Has been calculated .

Because the best route must meet 「 Monotone increasing 」, So we can use 「 Double pointer 」 Come on and Transfer at the same time , Each time the value is small, it will be updated , This ensures that the update process is also monotonous , That is, when it is necessary to calculate when , Than Small and Are transferred .

Code ：

class Solution {
    int MOD = (int)1e9 + 7;
    public int maxSum(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        long[] f = new long[n + 1], g = new long[m + 1];
        int i = 1, j = 1;
        while (i <= n || j <= m) {
            if (i <= n && j <= m) {
                if (nums1[i - 1] < nums2[j - 1]) {
                    f[i] = f[i - 1] + nums1[i - 1];
                    i++;
                } else if (nums2[j - 1] < nums1[i - 1]) {
                    g[j] = g[j - 1] + nums2[j - 1];
                    j++;
                } else {
                    f[i] = g[j] = Math.max(f[i - 1], g[j - 1]) + nums1[i - 1];
                    i++; j++;
                }
            } else if (i <= n) {
                f[i] = f[i - 1] + nums1[i - 1];
                i++;
            } else {
                g[j] = g[j - 1] + nums2[j - 1];
                j++;
            }
        }
        return (int) (Math.max(f[n], g[m]) % MOD);
    }
}

• Time complexity ：
• Spatial complexity ：

Last

This is us. 「 Brush through LeetCode」 The first of the series No.1537 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be accessed from the smart typesetting Gather new bases