题解 | 回文序列

#include <iostream>
using namespace std;

class Solution {
public:
    // 递归处理区间[head, tail]
    int makepalindrome(int* nums, int head, int tail) {
        int operations = 0;
        int left = nums[head];
        int right = nums[tail];
        
        // 当区间有效且两端不相等时
        while (head < tail && left != right) {
            if (left < right) {
                // 合并左侧
                head++;
                left += nums[head];
                operations++;
            } else {
                // 合并右侧
                tail--;
                right += nums[tail];
                operations++;
            }
        }
        
        // 如果区间已经重叠或交叉，返回当前操作次数
        if (head >= tail) return operations;
        
        // 否则递归处理内部区间
        return operations + makepalindrome(nums, head + 1, tail - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    int nums[50] = {0};
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    Solution solution;
    cout << solution.makepalindrome(nums, 0, n-1) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int makepalindrome(int[] nums, int head, int tail) {
            int operations = 0;
            int left = nums[head];
            int right = nums[tail];
            
            while (head < tail && left != right) {
                if (left < right) {
                    head++;
                    left += nums[head];
                    operations++;
                } else {
                    tail--;
                    right += nums[tail];
                    operations++;
                }
            }
            
            if (head >= tail) return operations;
            return operations + makepalindrome(nums, head + 1, tail - 1);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.makepalindrome(nums, 0, n-1));
        
        sc.close();
    }
}

def makepalindrome(nums, head, tail):
    operations = 0
    left = nums[head]
    right = nums[tail]
    
    # 当区间有效且两端不相等时
    while head < tail and left != right:
        if left < right:
            # 合并左侧
            head += 1
            left += nums[head]
            operations += 1
        else:
            # 合并右侧
            tail -= 1
            right += nums[tail]
            operations += 1
    
    # 如果区间已经重叠或交叉，返回当前操作次数
    if head >= tail:
        return operations
    
    # 否则递归处理内部区间
    return operations + makepalindrome(nums, head + 1, tail - 1)

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    print(makepalindrome(nums, 0, n-1))

if __name__ == "__main__":
    main()