preface
“This is the 20th day of my participation in the August Gwen Challenge.
1 Maximum Summation problem of NC19 subarrays (simple)
2. NC17 longest loop substring
Maximum summation problem of NC19 subarray
describe
Given an array arr, returns the maximum summation of subarrays
For example, arr = [1, -2, 3, 5, -2, 6, -1], all subarrays, [3, 5, -2, 6] can add up to the largest sum 12, so return 12.
They make sure that there are no numbers that are all negative numbers
[for]
Time is O(n)O(n), space is O(1)O(1)
Input:
[1, -2, 3, 5, -2, 6, -1]
Copy the code
Return value: 12
Analysis of ideas:
The maximal sum of subarrays ending with arr[I] depends on the maximal sum of subarrays ending with a[i-1] arr[I]
Define the dp array dp[I] to represent the maximum sum ending in arr[I]
dp[i] = Math.max(arr[i], dp[i-1] + arr[i])
Because dp[I] relates only to dp[i-1], a variable can be used instead of the dp array
AC code:
public int maxsumofSubarray(int[] arr) {
// write code here
if (arr == null || arr.length == 0) {
return 0;
}
int len = arr.length;
int ans = arr[0];
int dp = arr[0];
for (int i = 1; i < len; i++) {
dp = Math.max(arr[i], dp + arr[i]);
ans = Math.max(ans, dp);
}
return ans;
}
Copy the code
NC17 longest loop substring
describe
For a string, design an efficient algorithm to calculate the length of the longest loop substring.
Given A string A and its length n, return the length of the longest callback substring.
Example 1
Input:
"abc1234321ab",12
Copy the code
The return value:
7
Copy the code
Dp [I][j] is a palindrome from position I to position j
The value of dp[I][j] depends on whether chars[I] chars[j] is equal & dp[I +1][j-1]
When chars [I] is not equal to chars [j] that I and j do not constitute a palindrome, equal to dp [I] [j] = j – I = = 1 | | dp + 1] [I] [j – 1
Base case dp[I][j] = true when I ==j
Note that the value of the traversal direction dp[I][j] is related to her position in the lower left corner
Dp [I][j] = true Maximum palindrome length
AC code:
import java.util.*;
public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
boolean[][] dp = new boolean[n][n];
int maxLen = 1;
for (int i = 0; i < n; i++) dp[i][i] = true;
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if(A.charAt(i) ! = A.charAt(j))continue;
dp[i][j] = j - i == 1 || dp[i + 1][j - 1];
if (dp[i][j]) {
maxLen = Math.max(maxLen, j - i + 1); }}}returnmaxLen; }}Copy the code