package com.liuzhen.chapter8;

import java.util.ArrayList;

public class CoinRow {
    /*
     * 参数Money:给定硬币组合面值数
     * 函数功能：以数组链表形式返回最大总金额硬币组合的数组下标以及最大总金额，
     * 其中链表中最后一个元素为最大总金额，其它元素为硬币组合数组下标
     */
    public ArrayList<Integer> getMaxSumCoin(int[] Money){
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(Money.length == 1){             //当给定硬币个数只有一个时，最大总金额即为该枚硬币
            list.add(0);                   //存放硬币位置
            list.add(Money[0]);            //存放硬币总金额
            return list;
        }
        
        int[] tempMaxSum = new int[Money.length];     //用于存放遍历到当前硬币位置（从前到后遍历）的最大总金额
        tempMaxSum[0] = Money[0];
        if(Money[0] < Money[1])
            tempMaxSum[1] = Money[1];
        else
            tempMaxSum[1] = Money[0];
        
        for(int i = 2;i < Money.length;i++){
            if(tempMaxSum[i-1] >= tempMaxSum[i-2] + Money[i])
                tempMaxSum[i] = tempMaxSum[i-1];
            else
                tempMaxSum[i] = tempMaxSum[i-2] + Money[i];
        }
        
        System.out.println("n当前位置硬币的最大金额：");
        for(int i = 0;i < Money.length;i++)
            System.out.print(tempMaxSum[i]+" ");
        //根据tempMaxSum数组元素，找出，最大金额的硬币组合元素的数组下标
        for(int i = Money.length-2;i >=0;i--){
            int temp = tempMaxSum[i];
            if(temp < tempMaxSum[i+1]){
                list.add(i+1);             //存放最大金额硬币组合元素数组下标
                temp = tempMaxSum[i+1] - Money[i+1];
                for(int j = 0;j < Money.length;j++){   //寻找到tempMaxSum数组（从小到大排序）中第一个等于temp值的元素
                    if(tempMaxSum[j] == temp){
                        i = j;
                        break;
                    }
                }
            }
        }
        if(Money[0] >= Money[1])      //不管怎样选择硬币组合，在前两枚硬币中一定会选一枚
            list.add(0);
        else
            list.add(1);
        list.add(tempMaxSum[Money.length-1]);     //存放硬币最大总金额
        return list;
    }
    
    public static void main(String[] args){
        CoinRow test = new CoinRow();
        int[] Money = {1,1,2,10,6,2,10,8,12};
        
        System.out.println("当前位置硬币的金额：");
        for(int i = 0;i < Money.length;i++)
            System.out.print(Money[i]+" ");
        
        ArrayList<Integer> list = test.getMaxSumCoin(Money);
        
        System.out.println("n最大总金额硬币组合的数组下标依次为：");
        for(int i = 0;i < list.size()-1;i++)
            System.out.print(list.get(i)+" ");
        
        System.out.println("n最大总金额硬币组合的对象数组下标相应面值依次为：");
        for(int i = 0;i < list.size()-1;i++)
            System.out.print(Money[list.get(i)]+" ");
        
        System.out.println("n"+"最大总金额为：");
        System.out.println(list.get(list.size()-1));
    }
}

当前位置硬币的金额：
1 1 2 10 6 2 10 8 12 
当前位置硬币的最大金额：
1 1 3 11 11 13 21 21 33 
最大总金额硬币组合的数组下标依次为：
8 6 3 0 
最大总金额硬币组合的对象数组下标相应面值依次为：
12 10 10 1 
最大总金额为：
33