头条笔试题-数组两端轮流取数

目录

1. 输入描述
2. 输出描述
3. 输入示例
4. 备注

解法

题目描述

今天你将接受智慧老人的试炼，智慧老人先将n个数（a_1 … a_n)从左到右排成一排，然后从你开始，你俩依次从这排数中取走排头或排尾的数，直到n个数被取完为止，双方的得分为去走的数的和。（假设智慧老人足够聪明。）
请问你最多能得多少分呢？

输入描述

第一行有一个数字n，第二行有n个数字 a_1 .. a_n。

输出描述

一个数字：你的最大得分

输入示例

输入

3
1 1 1

输出

2

备注

数据范围

1 <= a_i <= 10000 for all i

对于n：

其中30%的数据：1<=n<=10

其中30%的数据：1<=n<=100(原题如此，可能是笔误)

其中40%的数据：1<=n<=2000

这里有类似的题目：
https://nanti.jisuanke.com/t/48

这里有一个解法，但是写有问题，数组会越界。

解法

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [][]sum = new int[n][n];
        int [][]dp  = new int[n][n];
        int []a     = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            dp[i][i] = a[i];
            sum[i][i] = a[i];
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                sum[i][j]=sum[i][j-1]+a[j];
            }
        }
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                dp[i][j]=sum[i][j]-Math.min(dp[i+1][j],dp[i][j-1]);
                dp[i][j]=sum[i][j]-Math.min(dp[i+1][j],dp[i][j-1]);
            }
        }
        System.out.println(dp[0][n-1]);
    }
}

计蒜客上那到题目只需把第 27 行改为

System.out.println(dp[0][n-1] + " " + (sum[0][n-1] - dp[0][n-1]));

就可以了。