1143. Longest Common Subsequence
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A 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.
For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.
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, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.
Original Page
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length()+1][text2.length()+1];
int res = 0;
for(int i=1; i<=text1.length(); i++){
for(int j=1; j<=text2.length(); j++){
dp[i][j] = dp[i-1][j];
if(text1.charAt(i-1) == text2.charAt(j-1)){
//i-1, j-1 means the previous text1 substring and the previous text2 substring
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
// Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
return dp[text1.length()][text2.length()];
}
1035. Uncrossed Lines
You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.
We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:
nums1[i] == nums2[j], and
the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).
Return the maximum number of connecting lines we can draw in this way.
Example 1:
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.
Example 2:
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3
Example 3:
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2
Constraints:
1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000
Original Page
This question is similar to the previous question, if the line does not cross, the max subsequence of the two given arrays will work as well.
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][] dp = new int[2][nums1.length+1];
for(int i=1; i<=nums2.length; i++){
for(int j=1; j<=nums1.length; j++){
if(nums1[j-1] == nums2[i-1]){
dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
}else{
dp[i%2][j] = Math.max(dp[i%2][j-1], dp[(i-1)%2][j]);
}
}
}
return dp[nums2.length%2][nums1.length];
}
53. Maximum Subarray
Given an integer array nums, find the
subarray
with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
Original Page
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
int res = dp[0];
for(int i=1; i<nums.length; i++){
dp[i] = Math.max(nums[i], dp[i-1]+nums[i]);
res = Math.max(res, dp[i]);
}
// System.out.println(Arrays.toString(dp));
return res;
}
Top comments (0)