This is a solution of week 1 for the Bitcoin and Cryptocurrency Technologies course (scrooge coin)

MaxFeeTxHandler.java

/**
 * This is a solution of week 1 for the Bitcoin and Cryptocurrency Technologies course (scrooge coin)
 * https://www.coursera.org/learn/cryptocurrency
 * Please, try yourself before looking this code
 * I was able to get 100/100 score!
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

public class MaxFeeTxHandler {

    /**
     * Creates a public ledger whose current UTXOPool (collection of unspent transaction outputs) is
     * {@code utxoPool}. This should make a copy of utxoPool by using the UTXOPool(UTXOPool uPool)
     * constructor.
     */
    private UTXOPool currentUtxoPool;

    public MaxFeeTxHandler(UTXOPool utxoPool) {
        currentUtxoPool = new UTXOPool(utxoPool);
    }

    private static double getFee(Transaction tx, UTXOPool pool) {
        double sumOfInputs = 0.0;
        for(int i = 0; i < tx.numInputs(); ++i) {
            Transaction.Input input = tx.getInput(i);
            UTXO utxo = new UTXO(input.prevTxHash, input.outputIndex);
            Transaction.Output output = pool.getTxOutput(utxo);
            sumOfInputs += output.value;
        }

        double sumOfOutputs = 0.0;
        for(int i = 0; i < tx.numOutputs(); ++i) {
            sumOfOutputs += tx.getOutput(i).value;
        }
        return sumOfInputs - sumOfOutputs;
    }

    private static UTXO getUtxo(Transaction tx, int inputIndex, UTXOPool pool) {
        Transaction.Input input = tx.getInput(inputIndex);
        return new UTXO(input.prevTxHash, input.outputIndex);
    }


    /**
     * @return true if:
     * (1) all outputs claimed by {@code tx} are in the current UTXO pool,
     * (2) the signatures on each input of {@code tx} are valid,
     * (3) no UTXO is claimed multiple times by {@code tx},
     * (4) all of {@code tx}s output values are non-negative, and
     * (5) the sum of {@code tx}s input values is greater than or equal to the sum of its output
     *     values; and false otherwise.
     */
    private static boolean isValidTx(Transaction tx, UTXOPool pool) {
        // (1)
        for(int i = 0; i < tx.numInputs(); ++i) {
            if(!pool.contains(getUtxo(tx, i, pool))) {
                return false;
            }
        }

        // (2)
        for(int i = 0; i < tx.numInputs(); ++i) {
            UTXO utxo = getUtxo(tx, i, pool);
            Transaction.Output output = pool.getTxOutput(utxo);
            if(!Crypto.verifySignature(output.address,
                    tx.getRawDataToSign(i),
                    tx.getInput(i).signature)) {
                return false;
            }
        }

        // (3)
        HashSet<UTXO> claimedSet = new HashSet<UTXO>();
        for(int i = 0; i < tx.numInputs(); ++i) {
            UTXO utxo = getUtxo(tx, i, pool);
            if(claimedSet.contains(utxo)) {
                return false;
            }
            claimedSet.add(utxo);
        }

        // (4)
        for(int i = 0; i < tx.numOutputs(); ++i) {
            if(tx.getOutput(i).value < 0.0) {
                return false;
            }
        }

        // (5)
        return getFee(tx, pool) >= 0.0;
    }

    public boolean isValidTx(Transaction tx) {
        return isValidTx(tx, currentUtxoPool);
    }



    private static void updatePool(Transaction possibleTx, UTXOPool pool) {
        // 1. remove used utxo
        for(int inputIdx = 0; inputIdx < possibleTx.numInputs(); ++inputIdx) {
            Transaction.Input input = possibleTx.getInput(inputIdx);
            UTXO utxo = new UTXO(input.prevTxHash, input.outputIndex);
            pool.removeUTXO(utxo);
        }

        // 2. add new utxo
        for(int outputIdx = 0; outputIdx < possibleTx.numOutputs(); ++outputIdx) {
            Transaction.Output ouput = possibleTx.getOutput(outputIdx);
            pool.addUTXO(new UTXO(possibleTx.getHash(), outputIdx), ouput);
        }
    }

    private Transaction[] _possibleTxs;
    private double _maxFee = 0.0;
    private int[] _bestTxIdList = null;

    private static int[] addElement(int[] a, int e) {
        a  = Arrays.copyOf(a, a.length + 1);
        a[a.length - 1] = e;
        return a;
    }

    private void handleTxsRecursive(UTXOPool pool, int indexStart, int[] seletectedTxIds, Double totalFee) {
        if(totalFee > _maxFee) {
            _maxFee = totalFee;
            _bestTxIdList = seletectedTxIds;
        }

        for(int i = indexStart; i < _possibleTxs.length; ++i) {
            Transaction tx = _possibleTxs[i];
            if(isValidTx(tx, pool)) {
                UTXOPool copyPool = new UTXOPool(pool);
                updatePool(_possibleTxs[i], copyPool);
                int [] extendedList = addElement(seletectedTxIds, i);
                double fee = getFee(tx, pool);
                handleTxsRecursive(copyPool, i + 1, extendedList, totalFee + fee);
            }
        }
    }

    /**
     * Handles each epoch by receiving an unordered array of proposed transactions, checking each
     * transaction for correctness, returning a mutually valid array of accepted transactions, and
     * updating the current UTXO pool as appropriate.
     */
    public Transaction[] handleTxs(Transaction[] possibleTxs) {
        _possibleTxs = possibleTxs;
        _maxFee = -1.0;
        _bestTxIdList = new int[0];

        handleTxsRecursive(currentUtxoPool, 0, _bestTxIdList, 0.0);

        ArrayList<Transaction> results = new ArrayList<Transaction>();

        if(_bestTxIdList != null) {
            for(int i = 0; i < _bestTxIdList.length; ++i) {
                results.add(_possibleTxs[_bestTxIdList[i]]);
            }
        }

        Transaction[] r = new Transaction[results.size()];
        results.toArray(r);
        return r;
    }
}