本文共 2886 字，大约阅读时间需要 9 分钟。

题目一：连续最大和

一个数组有 N 个元素，求连续子数组的最大和。例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3。解决这个问题的关键在于找到数组中最长的连续正数子数组的和。

首先，我们可以通过遍历数组的每个元素，维护一个当前和当前的最大值。具体来说，我们从数组的第一个元素开始，逐步累加当前元素的值到当前和中。如果当前和大于等于最大值，我们就更新最大值。这种方法的时间复杂度为 O(N)，非常高效。

import java.util.*;
public class Main {
    public static int getMax(int[] arr) {
        int max = arr[0];
        int current = arr[0];
        for (int i = 1; i < arr.length; i++) {
            current += arr[i];
            if (current > max) {
                max = current;
            }
        }
        return max;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        System.out.println(getMax(arr));
    }
}

题目二：统计回文

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。

要解决这个问题，我们可以逐一尝试将字符串B插入字符串A的所有可能位置，然后检查每个新形成的字符串是否是回文。具体来说，我们可以遍历字符串A的每个位置（包括前后），将字符串B插入到当前位置，形成一个新的字符串。然后用新字符串的反转版本与原字符串比较，如果相等，则说明这是一个回文。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str1 = scan.nextLine();
        String str2 = scan.nextLine();
        int count = 0;
        for (int i = 0; i <= str1.length(); i++) {
            StringBuffer sb = new StringBuffer(str1);
            sb.insert(i, str2);
            String temp = sb.toString();
            if (new StringBuffer(temp).reverse().toString().equals(temp)) {
                count++;
            }
        }
        System.out.println(count);
    }
}

题目三：不要二

有一个W×H的网格盒子，网格的行编号为0到H-1，列编号为0到W-1。每个格子至多可放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为√[(x1-x2)^2 + (y1-y2)^2]，最多可以放多少块蛋糕在网格盒子里。

这个问题需要通过数学分析来解决。首先，我们需要找出网格中互不冲突的蛋糕放置方式。由于两块蛋糕的欧几里得距离不能等于2，这意味着它们的坐标差的平方和不能等于4。因此，任何两个放置的蛋糕不能满足(x1-x2)^2 + (y1-y2)^2 = 4。

通过分析，我们可以发现最优的放置方式是每隔一个格子放置一块蛋糕。具体来说，我们可以按照棋盘格的方式放置蛋糕，使得任何两块蛋糕之间的距离都大于2。这种方法可以最大化蛋糕的数量。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int w = scan.nextInt();
        int h = scan.nextInt();
        int[][] grid = new int[w][h];
        // 初始化棋盘格
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                if ((i + j) % 2 == 0) {
                    grid[i][j] = 1;
                } else {
                    grid[i][j] = 0;
                }
            }
        }
        int count = 0;
        // 遍历每个格子
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}