【网易笔试题】游戏卡牌

解题思路

首先测试样例有错误，应该是

输入
5
1 2 3 4 5
10
输出
30

暴力解，找到所有和为m的求积。

import java.util.Scanner;
import java.util.HashMap;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] data = new long[n];
        for (int i = 0; i < n; i++)
            data[i] = sc.nextInt();
        long m = sc.nextInt();

        long max = 0;
        HashMap<Long, Long> list = new HashMap<>();

        int index = 0;
        while (index < n && data[index] == 0) {
            index++;
        }
        if (index < n) {
            list.put(data[index], data[index]);
            if (data[index] == m)
                max = data[index];
        }
        for (int i = index + 1; i < n; i++) {

            if (data[i] == 0)
                continue;
            if (data[i] == m && data[i] > max)
                max = data[i];
            Iterator<Long> listIterator = list.keySet().iterator();

            HashMap<Long, Long> buffer = new HashMap<Long, Long>();
            while (listIterator.hasNext()) {

                Long num = listIterator.next();
                long multi = list.get(num) * data[i];
                long a = 0;
                if ((a = num + data[i]) < m) {
                    if (list.containsKey(a)) {
                        if (multi > list.get(a)) {
                            buffer.put(a, multi);
                        }
                    } else {
                        buffer.put(a, multi);
                    }
                } else if (a == m) {
                    if (max < multi)
                        max = multi;
                }
            }
            list.putAll(buffer);
            if (list.containsKey(data[i])) {
                if (list.get(data[i]) < data[i]) {
                    list.put(data[i], data[i]);
                }
            } else {
                list.put(data[i], data[i]);
            }
        }
        System.out.println(max == 0 ? -1 : max);
    }
}