⭐️连续最大和⭐️

🔐题目详情

描述

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

输入描述：

输入为两行。 第一行一个整数 n(1 <= n <= 100000)，表示一共有 n 个元素 第二行为 n 个数，即每个元素,每个整数都在 32 位 int 范围内。以空格分隔。

输出描述：

所有连续子数组中和最大的值。

示例 1

输入：

3-1 2 1

输出：

3

题目链接：连续最大和

💡解题思路

基本思路： 动态规划

解题思路：本题需要我们去求一段连续子序列的最大连续和，我们可以考虑动态规划，假设有一数组arr，长度为n，下标为i。做动态规划题，有三个步骤：

• 状态定义

• 确定初始状态

• 确定状态转移方程

类似与数学推理，我们要相信，人可能会欺骗我，生活可能会欺骗我，但是数学永远不会欺骗我们，所以在下面进行推理的时候，只要你推理过程没有问题，要坚信你得到的推理表达式是正确的，如果你得到的状态转移方程有问题，你就要想想，你状态定义的是否为题目直接所求，你的初始状态是否正确，你的推理逻辑是否严密。

下面我们来进行推导：

状态定义： 我们定义$f[i]$表示以$i$下标元素结尾的最大连续子序列和。确定初始状态： 当$i=0$时，$f[0]=arr[0]$。转态转移方程：

遍历到$i$下标的元素的时候，你有两种选择，一是在原来序列上加上这一个元素，此时的序列和为$f[i-1]+arr[i]$，另外的一种选择就是放弃之前的序列，从当前元素开始新的序列，此时序列和为$arr[i]$，我们要选择哪一种呢?很明显，我们选择序列和更大的那一个，因此状态转移方程也就出来了。

再次回到我们的题目，题目让我们求最大连续子序列的和，我们状态转移方程求的是以i下标元素结尾的连续子序列最大和，因此整个数组的连续子序列最大和，就是从i下标元素结尾的最打连续子序列和中最大的那一个，即所求得f[n]数组中最大的元素。

🔑源代码

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();        }        //转态定义:定义f[i]表示以i作为结尾下标的元素的最大序列和        //初始状态确定:当i=0时，最大元素和为f[0] = arr[0]        //状态转移方程f[i] = Max(f[i - 1] + arr[i], arr[i])        int[] f = new int[n];        f[0] = arr[0];        //ans用来求最大子连续序列和        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];                        //如果当前以i结尾的最大序列和比ans大，则更新，否则不更新            ans = f[i] > ans ? f[i] : ans;        }        System.out.println(ans);    }}

🌱总结

本题为简单动态规划推理题，重点是要学会如何进行状态定义，如何确定初始状态值，如何推导状态转移方程。类似题：53. 最大子数组和509. 斐波那契数剑指 Offer 10- II. 青蛙跳台阶问题118. 杨辉三角119. 杨辉三角 II121. 买卖股票的最佳时机70. 爬楼梯1137. 第 N 个泰波那契数

升级题：剑指 Offer II 088. 爬楼梯的最少成本

⭐️判断回文⭐️

🔐题目详情

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串 A 和字符串 B。现在她非常好奇有没有办法将字符串 B 插入字符串 A 使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串 B 插入的位置不同就考虑为不一样的办法。例如：A = “aba”，B = “b”。这里有 4 种把 B 插入 A 的办法：* 在 A 的第一个字母之前: "baba" 不是回文* 在第一个字母‘a’之后: "abba" 是回文* 在字母‘b’之后: "abba" 是回文* 在第二个字母'a'之后 "abab" 不是回文所以满足条件的答案为 2

输入描述：

每组输入数据共两行。 第一行为字符串 A 第二行为字符串 B 字符串长度均小于 100 且只包含小写字母

输出描述：

输出一个数字，表示把字符串 B 插入字符串 A 之后构成一个回文串的方法数

示例 1

输入：

abab

输出：

2

💡解题思路

基本思路： 模拟构造+判断回文解题思路：不妨设题目中的A字符串为str1，B字符串为str2，首先我们考虑每一个位置，str2插入str1指定位置构造字符串，然后判断这个构造的字符串是否回文即可，如果为回文字符串，计数器加1即可。

对于判断回文，很简单，就是将字符串逆置，在于源字符串比较，如果相同，那这个字符串就是回文字符串。

🔑源代码

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);    }}

🌱总结

本题为字符串模拟题，基本思路就是构造str2插入str1字符串每一个位置情况的字符串，然后判断回文并计数即可。类似题：125. 验证回文串剑指 Offer II 027. 回文链表

升级题：剑指 Offer II 020. 回文子字符串的个数