当前位置：网站首页>Continuous maximum sum and judgement palindrome

Continuous maximum sum and judgement palindrome

2022-07-25 05:22:00 【InfoQ】

️ Continuous maximum sum ️

Topic details

describe

An array has N Elements , Find the maximum sum of successive subarrays . for example ：[-1,2,1], And the largest continuous subarray is [2,1], The sum is 3

Input description ：

Enter in two lines . The first line is an integer n(1 <= n <= 100000), Means that there are n Elements Second behavior n Number , That is, every element , Every integer is in 32 position int Within the scope of . Space off .

Output description ：

The largest value in all successive subarrays .

Example 1

Input ：

3
-1 2 1

Output ：

Topic link ：

Continuous maximum sum

Their thinking

The basic idea ：

Dynamic programming

Their thinking ：

This problem requires us to find the maximum continuous sum of a continuous subsequence , We can consider dynamic programming , Suppose you have an array

arr

, The length is

n

, Subscript to be

i

. Do dynamic planning problems , There are three steps ：

State definition

Determine the initial state

Determine the state transfer equation

Similar to mathematical reasoning , We have to believe , People may cheat me , Life may deceive me , But mathematics will never deceive us , So when reasoning below , As long as your reasoning process is ok , Be sure that the reasoning expression you get is correct , If you get a problem with the state transition equation , You have to think about it , Whether your status definition is directly required by the topic , Is your initial state correct , Whether your reasoning logic is rigorous .

Now let's deduce ：

State definition ：

We define

Said to

The sum of the largest continuous subsequence at the end of the subscript element .

Determine the initial state ：

When

when ,

The transition equation ：

Traversing

Subscript element , You have two options , One is to add this element to the original sequence , At this time, the sequence sum is

, Another option is to abandon the previous sequence , Start a new sequence from the current element , At this time, the sequence sum is

, Which one should we choose ? Obviously , We choose the sequence and the larger one , So the state transition equation comes out .

Back to our topic again , Let's find the sum of the largest continuous subsequences , Our state transition equation is solved by

i

The maximum sum of consecutive subsequences at the end of the subscript element , Therefore, the maximum sum of continuous subsequences of the entire array , It's from

i

The largest of the most contiguous subsequences at the end of the subscript element , That is, the obtained

f[n]

The largest element in the array .

Source code

import java.util.*;
public class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 int n = sc.nextInt();
 int[] arr = new int[n];
 
 for (int i = 0; i < n; i++) {
 arr[i] = sc.nextInt();
 }
 // Transition definition : Definition f[i] Said to i The maximum sequence sum of the elements as the ending subscript 
 // The initial state is determined : When i=0 when , The largest sum of elements is f[0] = arr[0]
 // State transition equation f[i] = Max(f[i - 1] + arr[i], arr[i])
 int[] f = new int[n];
 f[0] = arr[0];
 //ans Used to find the sum of maximal sub continuous sequences 
 int ans = arr[0];
 for (int i = 1; i < n; i++) {
 int curval = f[i - 1] + arr[i];
 f[i] = curval > arr[i] ? curval : arr[i];
 
 // If currently i The maximum sequence sum ratio at the end ans Big , Update , Otherwise, it will not be updated 
 ans = f[i] > ans ? f[i] : ans;
 }
 System.out.println(ans);
 }
}

summary

This is a simple dynamic programming reasoning problem , The key is to learn how to define States , How to determine the initial state value , How to derive the state transition equation . Similar questions ：

53. Maximum subarray and

509. Fibonacci number

The finger of the sword Offer 10- II. The problem of frog jumping on the steps

118. Yang hui triangle

119. Yang hui triangle II

121. The best time to buy and sell stocks

70. climb stairs

1137. The first N One tibonacci number

Upgrade questions ：

The finger of the sword Offer II 088. The least cost of climbing stairs

️ Palindrome ️

Topic details

“ Palindrome string ” It's a string that is read both forward and backward , such as “level” perhaps “noon” And so on are palindrome strings . Hua Hua likes this palindrome string with symmetrical beauty very much , On her birthday, she got two gifts, one was string A And string B. Now she is very curious about whether there is any way to put the string B Insert string A Make the resulting string a palindrome string . You accept Huahua's request , Help her find out how many ways to insert a new string into a palindrome string . If the string B If the insertion position is different, it will be considered as different methods . for example ：A = “aba”,B = “b”. Here you are 4 Plant a handle B Insert A The way to ：* stay A Before the first letter of : "baba" Not a palindrome * In the first letter ‘a’ after : "abba" It's palindrome. * In the letters ‘b’ after : "abba" It's palindrome. * In the second letter 'a' after "abab" It's not palindrome, so the answer that meets the condition is 2

Input description ：

Each group has two lines of input data . The first line is string A The second behavior string B String length is less than 100 And contain only lowercase letters

Output description ：

Output a number , Represents a string B Insert string A Then the number of methods to form a palindrome string

Example 1

Input ：

aba
b

Output ：

Their thinking

The basic idea ：

Simulate construction + Palindrome

Their thinking ：

You might as well set

A

String is

str1

B

String is

str2

, First, let's consider each location ,

str2

Insert

str1

Specify the position construction string , Then judge whether the constructed string is palindrome , If it is palindrome string , Counter plus

1

that will do .

For judging palindromes , It's simple , Is to reverse the string , Lies in the source string comparison , If the same , Then this string is the palindrome string .

Source code

import java.util.*;

public class Main{
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 String str1 = sc.nextLine();
 String str2 = sc.nextLine();
 
 int ans = 0;
 int n = str1.length();
 for (int i = 0; i <= n; i++) {
 StringBuilder sb = new StringBuilder();
 sb.append(str1.substring(0, i));
 sb.append(str2);
 sb.append(str1.substring(i, n));
 String rs1 = sb.toString();
 String rs2 = sb.reverse().toString();
 if (rs1.equals(rs2)) {
 ans++;
 }
 }
 System.out.println(ans);
 }
}