Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.
Note that the subarray needs to be non-empty after deleting one element.
Input: arr = [1,-2,0,3]
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.
Input: arr = [1,-2,-2,3]
Explanation: We just choose  and it's the maximum sum.
Input: arr = [-1,-1,-1,-1]
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.
1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4
First, handle the special case: all numbers are negative, return the max one.
s0 = max subarray sum ends with a[i] s1 = max subarray sum ends with a[i] with at most one deletion
whenever s0 or s1 becomes negative, reset them to 0.
Given two strings text1 and text2, return the length of their longest common subsequence.
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. (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.
Input: text1 = "abcde", text2 = "ace"
Explanation: The longest common subsequence is "ace" and its length is 3.
Input: text1 = "abc", text2 = "abc"
Explanation: The longest common subsequence is "abc" and its length is 3.
Input: text1 = "abc", text2 = "def"
Explanation: There is no such common subsequence, so the result is 0.
1 <= text1.length <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.
Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i] and text2[0:j] dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])
Time complexity: O(mn) Space complexity: O(mn) -> O(n)