private long search(int[] nums) {
        if (nums.length == 1) return nums[0];
        String key = buildKey(nums);
        if (cache.containsKey(key)) return cache.get(key);
        long max = 0, maxIndex = 0;
        for (int i = 0; i < nums.length; ++i) {
            int self = i == 0 ? nums[i] * nums[i + 1] : i == nums.length - 1 ? nums[i] * nums[i - 1] : nums[i - 1] * nums[i] * nums[i + 1];
            long next = search(buildArray(nums, i));
            if (self + next > max) {
                max = self + next;
                maxIndex = i;
            }
        }
        cache.put(key, max);
        return max;
    }