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