**

2020年阿里巴巴实习生线上笔试试题

**

题目描述：n个人排成一排，每个人都拥有自己的能量值，越靠前的能量值越高。每个人可以崇拜唯一的能量值比他高的人，也可以没有崇拜对象。现在n个人进行投票，每个人可以投自己或者是跟着崇拜对象进行投票，求出每个人可能得到的最多票数。

输入：第一行为人数n，是一个正整数；第二行Ai(1<=i<=n)为第n个人的崇拜对象，是一个整数，之间用空格分隔。
输出：n行整数，第i行为第i个人能得到的最多票数。

示例：
输入：
4
0 1 1 1
输出：
4
1
1
1

题目解析：
首先我们想到用int型数组存放第二行输入的整数，可以得到一个具有崇拜关系的数组，其次定义一个长度为n的存放第n个人能得到的最大票数的数组。那么，数组中每个元素的值到死如何确定呢？由于每个人无论有无崇拜的人，都可以给自己投一票，于是我们可以把数组中所有元素初始化为1。那么如何才能确定数组中每一个元素最终的值呢？这取决于崇拜这个人的人能给他投的票数到底有多少，但是崇拜是有条件的，即：所有人只能崇拜能量值比他高的人，也就是说排在前面的人的票数其实是跟排在后面的人所能投的票数息息相关的。便想到采用逆序遍历和修改数组的方法解决此问题！

代码如下：

package practice;
import java.util.Scanner;
public class test1 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int shuru[]=new int[n+1];		//存放n个人的崇拜对象
		shuru[0]=-1;
		for(int i=1;i<=n;i++) {
			shuru[i]=input.nextInt();		//存放每个人当前拥有的票数
		}
		int piaoshu[]=new int[n+1];
		piaoshu[0]=-1;
		for(int i=1;i<=n;i++) {
			piaoshu[i]=1;					//初始化每个人至少有来自自己的那一票
		}
		/*选择从后往前访问和修改数组，原因是排在后面的人可能崇拜排在其前面的人，排在前面的人的票数会受到后面的人的影响
		 * 逆序访问数组方可解决此问题*/
		for(int i=n;i>=1;i--) {
			if(shuru[i]!=0) {	/*shuru[i]等于0，说明没有崇拜对象，能得到的最大票数就是当前拥有的票数。shuru[i]
			不等于0，说明此人所有崇拜的人，崇拜的人的票数应该加上此人当前的票数*/	
			//piaoshu[shuru[i]]表示第i个人所崇拜的人的当前票数
				piaoshu[shuru[i]]+=piaoshu[i];
			}
		}
		for(int i=1;i<=n;i++) {
			System.out.println(piaoshu[i]);
		}
	}
}

测试及分析：

分析：
5
0 1 2 3 1
5
3
2
1
1

初始化，5个人的当前票数为：1 1 1 1 1
逆序遍历数组：
（1）第五人崇拜第一人，第一人票数加上第五人的当前票数，
此时当前票数为：2 1 1 1 1
（2）第四人崇拜第三人，第三人票数加上第四人的当前票数，
此时当前票数为：2 1 2 1 1
（3）第三人崇拜第二人，第二人票数加上第三人的当前票数，
此时当前票数为：2 3 2 1 1
（4）第二人崇拜第一人，第一人票数加上第二人的当前票数，
此时当前票数为：5 3 2 1 1
（5）第五人无崇拜对象，不变
遍历完成，最终每个人能得到的最多票数为：5 3 2 1 1