918. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Note:

1. -30000 <= A[i] <= 30000
2. 1 <= A.length <= 30000

---

给定一个循环数组，即数组的最后一个和数字第一个连起来了。求循环数组的最大连续子数组和。

LeetCode Maximum Subarray的升级版，即数组首尾相连了。我一开始想到的解法是，既然数组首尾相连了，那就2*n次dp即可，即把原数组复制一遍，接到原数组后面，形成2*n长的数组，然后照样跑原来的DP算法。这个解法是不对的，比如如果数组是[1,2,3,4]这种全是正数，则跑2n遍之后，ans会一直max更新，导致最后的ans是1+…+4+1+…4，即数组加了两遍，每个数重复加了。另外对于数组[5,-3,5]这种，也会完整数组加两遍。

正确解法是，分两种情况，第一种情况是最大子串和没有跨越首尾，则使用常规DP即可求解。第二种情况是，最大子串和跨越了首尾，则可以把问题转化为求原数组的最小连续子串和，然后用数组总和减去最小连续子串和，就能得到跨越首尾的最大连续子串和。在求解第二种情况时，需要注意如果最小连续子串和是整个数组的情况，比如数组都是负数[-1,-2,-3]，则求到的最小连续子串和是整个数组[-1,-2,-3]，用数组总和一减变成了空集和为0，但最大连续子串和至少需要1个元素，对于这种情况，丢弃case2的解。

完整代码如下：

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        vector<int> dp(n, 0);
        
        // 最大连续子串
        dp[0] = A[0];
        int ans1 = A[0], sum = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = max(dp[i - 1], 0) + A[i];
            ans1 = max(ans1, dp[i]);
            
            sum += A[i];
        }
        
        // 最小连续子串
        fill(dp.begin(), dp.end(), 0);
        dp[0] = A[0];
        int ans2 = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = min(dp[i - 1], 0) + A[i];
            ans2 = min(ans2, dp[i]);
        }
        
        if(ans2 == sum) ans2 = INT_MIN; // 注意最小连续子串和不能是全长数组
        else ans2 = sum - ans2;
        
        return max(ans1, ans2);
    }
};

本代码提交AC，用时252MS。

1458. Max Dot Product of Two Subsequences

Given two arrays nums1 and nums2.

Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

Example 1:

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

Example 2:

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.

Example 3:

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

Constraints:

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 1000

---

给定两个数组，问从这两个数组中选出两个长度相同的子序列，使得子序列的向量点积最大，求这个最大值。

难题，参考讨论区解法： https://leetcode.com/problems/max-dot-product-of-two-subsequences/discuss/648261/C++Python-Simple-DP 。

假设dp[i][j]表示nums1[0:i]和nums2[0:j]的最大点积。则在求解dp[i][j]时，有以下四种情况：

• 不选nums1第i个数，dp[i][j]=dp[i-1][j]
• 不选nums2第j个数，dp[i][j]=dp[i][j-1]
• 既不选nums1第i个数，也不选nums2第j个数，dp[i][j]=dp[i-1][j-1]
• 既选nums1第i个数，也选nums2第j个数，dp[i][j]=dp[i-1][j-1]+nums1[i]*nums2[j]

在最后一个情况中，如果dp[i-1][j-1]<0的话，就把前面的点积都扔掉，相当于max(dp[i-1][j-1],0)，完整代码如下：

class Solution {
public:
	int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));
		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
				dp[i][j] = max(dp[i][j], dp[i][j - 1]);
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
				dp[i][j] = max(dp[i][j], max(dp[i - 1][j - 1], 0) + nums1[i - 1] * nums2[j - 1]);
			}
		}
		return dp[m][n];
	}
};

本代码提交AC，用时96MS。

1423. Maximum Points You Can Obtain from Cards

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

---

给定一个数组，要从中选k个数，每次只能从左边选或从右边选，问选出的数的和最大是多少。

转换思路，无论从左边选多少个，从右边选多少个，剩余的数都是中间区域的某一段数。要使选出来的数和最大，则相当于要使剩下的连续区间的数和最小。所以可以设置一个大小为n-k的滑动窗口，求该滑动窗口的最小和，则用总和减去该最小和即为最终结果。

完整代码如下：

class Solution {
public:
	int maxScore(vector<int>& cardPoints, int k) {
		int sum = 0, n = cardPoints.size();
		for (int i = 0; i < n; ++i)sum += cardPoints[i];
		if (k == n)return sum;

		int min_window_sum = 0, i = 0, j = n - k - 1;
		for (int k = i; k <= j; ++k)min_window_sum += cardPoints[k];
		int cur_window_sum = min_window_sum;
		while (j < n) {
			if (j == n - 1)break;
			cur_window_sum = cur_window_sum + cardPoints[++j] - cardPoints[i++];
			min_window_sum = min(min_window_sum, cur_window_sum);
		}
		return sum - min_window_sum;
	}
};

本代码提交AC，用时152MS。

我之前的想法一直是正向思维，即模拟每次拿左边或右边，甚至还用DP来求解，但都无果。

看讨论区后还是很有启发，无论你当前这一步是拿左边还是右边，经过k轮之后的最终效果是，左边拿了连续的a的，右边拿了连续的k-a个。所以只需要对最终左边拿了几个进行DP建模，而无需模拟每一步是拿了左边还是右边。DP方法可看讨论区： https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/discuss/598111/Java-dp-solution(explanation-with-picture) 。

5383. Number of Ways to Paint N × 3 Grid

You have a grid of size n x 3 and you want to paint each cell of the grid with exactly one of the three colours: Red, Yellow or Green while making sure that no two adjacent cells have the same colour (i.e no two cells that share vertical or horizontal sides have the same colour).

You are given n the number of rows of the grid.

Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 12
Explanation: There are 12 possible way to paint the grid as shown:

Example 2:

Input: n = 2
Output: 54

Example 3:

Input: n = 3
Output: 246

Example 4:

Input: n = 7
Output: 106494

Example 5:

Input: n = 5000
Output: 30228214

Constraints:

• n == grid.length
• grid[i].length == 3
• 1 <= n <= 5000

---

给定3种颜色，要求涂满N*3的网格，且相邻网格的颜色不能一样，问有多少种涂法。

首先，如果只有一行的话。如果涂3种颜色，则因为3种颜色各不相同，所以有3种排列的方法，共3!=6种。如果涂2种颜色，则相同的颜色涂两边，不同的颜色涂中间，首先从3种颜色中选2种，为$C_3^2$，2种颜色决定哪个放中间有2种方法，所以也有6种涂法。

对于涂3种颜色的一行，其下一行可以涂2种颜色，有2种涂法；也可以涂3种颜色，也有2种涂法。

对于涂2种颜色的一行，其下一行可以涂2种颜色，有3种涂法；也可以涂3种颜色，有2种涂法。

综合上面两种情况，下一行是2种颜色的情况=上一行是3种颜色*2+上一行是2种颜色*3，类似的，下一行是3种颜色的情况=上一行是3种颜色*2+上一行是2种颜色*2。根据递推公式，最终的情况数是两者相加，代码如下：

class Solution {
public:

	int numOfWays(int n) {
		if (n == 1)return 12;
		long long pre_two_colors = 6, pre_three_colors = 6;
		long long mod = 1e9 + 7;
		for (int i = 2; i <= n; ++i) {
			long long next_two_colors = 3 * pre_two_colors + 2 * pre_three_colors;
			long long next_three_colors = 2 * pre_two_colors + 2 * pre_three_colors;
			pre_two_colors = next_two_colors % mod;
			pre_three_colors = next_three_colors % mod;
		}
		return (pre_two_colors + pre_three_colors) % mod;
	}
};

本代码提交AC，用时0MS。

参考：

• https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/discuss/574932/simple-solution-with-pictures
• https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/discuss/574923/JavaC++Python-DP-O(1)-Space
• https://www.geeksforgeeks.org/ways-color-3n-board-using-4-colors/ 4种颜色的情况类似