⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【连续最大和】和【判断回文】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆首发时间：🌴2022年7月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《数据结构与算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️连续最大和⭐️

🔐题目详情

描述

一个数组有 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]$，我们要选择哪一种呢?很明显，我们选择序列和更大的那一个，因此状态转移方程也就出来了。

$$f[i]=max(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. 杨辉三角 II
121. 买卖股票的最佳时机
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

输入：

aba
b

输出：

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. 回文子字符串的个数