# LeetCode Maximum Length of Subarray With Positive Product

1567. Maximum Length of Subarray With Positive Product

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.


Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].


Example 4:

Input: nums = [-1,2]
Output: 1


Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4


Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
vector<int> dp_pos(n, 0), dp_neg(n, 0);
if(nums[0] > 0) dp_pos[0] = 1;
else if(nums[0] < 0) dp_neg[0] = 1;
int ans = dp_pos[0];
for(int i = 1; i < n; ++i) {
if(nums[i] > 0) {
dp_pos[i] = dp_pos[i - 1] + 1;
dp_neg[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
} else if(nums[i] < 0) {
dp_pos[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
dp_neg[i] = dp_pos[i - 1] + 1;
}
ans = max(ans, dp_pos[i]);
}
return ans;
}
};

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
int pos_len = 0, neg_len = 0;
if(nums[0] > 0) pos_len = 1;
else if(nums[0] < 0) neg_len = 1;
int ans = pos_len;
for(int i = 1; i < n; ++i) {
if(nums[i] > 0) {
++pos_len;
neg_len = neg_len > 0 ? neg_len + 1 : 0;
} else if(nums[i] < 0) {
int tmp = pos_len;
pos_len = neg_len > 0 ? neg_len + 1 : 0;
neg_len = tmp + 1;
} else if(nums[i] == 0) {
pos_len = neg_len = 0;
}
ans = max(ans, pos_len);
}
return ans;
}
};

# 剑指 Offer 14- I. 剪绳子 LCOF

2 <= n <= 58

class Solution {
public:
int cuttingRope(int n) {
if(n <= 3) return n - 1;
int m = n / 3;
if(n % 3 == 0) {
return pow(3, m);
} else if(n % 3 == 1) {
return pow(3, m - 1) * 4;
} else {
return pow(3, m) * 2;
}
}
};

class Solution {
public:
int cuttingRope(int n) {
vector<int> dp(n + 1, 0);
dp[1] = 1;
for(int i = 2; i <= n; ++i) {
for(int j = 1; j < i; ++j) {
dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
}
}
return dp[n];
}
};

# 剑指 Offer 10- II. 青蛙跳台阶问题

0 <= n <= 100

class Solution {
public:
int numWays(int n) {
if(n == 0) return 1;
if(n == 1) return 1;
if(n == 2) return 2;
int a = 1, b = 2;
for(int i = 3; i <= n; ++i) {
int tmp = (a + b) % 1000000007;
a = b;
b = tmp;
}
return b;
}
};

# 剑指 Offer 10- I. 斐波那契数列

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.

0 <= n <= 100

class Solution {
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
long long a = 0, b = 1;
for(int i = 2; i <= n; ++i) {
long long tmp = a + b;
tmp %= 1000000007;
a = b;
b = tmp;
}
return b;
}
};

typedef long long LL;

class Solution {
private:
vector<vector<LL>> multiply(vector<vector<LL>> &m1, vector<vector<LL>> &m2) {
int n = m1.size();
vector<vector<LL>> ans(n, vector<LL>(n, 0));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
for(int k = 0; k < n; ++k) {
ans[i][j] += m1[i][k] * m2[k][j] % 1000000007;
}
}
}
return ans;
}
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;

vector<vector<LL>> matrix = {{1,1},{1,0}};

vector<vector<LL>> ans = {{1,0},{0,1}};
while(n != 0) {
if(n % 2 == 1) ans = multiply(ans, matrix);
matrix = multiply(matrix, matrix);
n >>= 1;
}

return ans[0][1] % 1000000007;
}
};

# LeetCode Maximum Sum Circular Subarray

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]这种，也会完整数组加两遍。

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);
}
};

# LeetCode Coin Change 2

518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1


Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.


Example 3:

Input: amount = 10, coins = [10]
Output: 1


Note:

You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

LeetCode Coin Change类似，也用动态规划。假设dp[i][j]表示用前i硬币，凑齐j块钱的方案数。则有两种情况，一是不用第i类硬币，有dp[i-1][j]种情况；二是用第i类硬币，则还需要凑齐j-coins[i]块钱，因为每类硬币无穷个，所以还是用前i类硬币凑齐j-coins[i]块钱，即有dp[i][j-coins[i]]种情况。两种情况数相加即可。完整代码如下：

class Solution {
public:
int change(int amount, vector<int>& coins) {
if(amount == 0) return 1;
int n = coins.size();
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
for(int i = 0; i <= n; ++i) dp[i][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= amount; ++j) {
dp[i][j] = dp[i - 1][j];
if(j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
}
}
return dp[n][amount];
}
};

# LeetCode Max Dot Product of Two Subsequences

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

• 不选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]

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];
}
};

# LeetCode Maximum Points You Can Obtain from Cards

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

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;
}
};

# LeetCode Longest Common Subsequence

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.


Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.


Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.


Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
int a = dp[i - 1][j], b = dp[i][j - 1], c = dp[i - 1][j - 1];
if (text1[i - 1] == text2[j - 1])++c;
dp[i][j] = max(max(a, b), c);
}
}
return dp[m][n];
}
};


# LeetCode 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: RedYellow 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

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;
}
};