作业帮二面手撕代码题答案-----由一篇凉经诞生我的第一篇博客

/**

• 作业帮二面代码题：
• 给定两个等长数组Y和A；其中Y中的元素都在1-50范围内且为正整数
• A中的元素都为实数-10000-10000，各自数组都有可重复
• 选取一组下标集合{0,1,2,...n},使得子数组Y’的不同元素乘以A’元素之和的值最大，输出最大值
• 即使得count(distinct Y[i])*sum(A[i])
• 举例说明：
  假如Y：{1，2，3} A：{7，4，-1}

    最大结果：（7+4-1）*count(distinct（1，2，3）)=30

  假如Y：{1，1，1, 5, 5, 4} A：{4，-7，4, 4, 1}

   最大结果：（4+4+1）*count(distinct（5，5，4）)=18

• /

思路解析：先分别得到构造两个辅助数组，一个记录Y的从index位置到数组最后 这个子数组中不重
复的个数；另一个辅助数组记录A的从index位置到数组最后 这个子数组中累加和
然后暴力遍历每一个Index即可

public class CountDistinctYsumA {
//测试代码
public static void main(String[] args) {
int[] arrA={4,-7,4,4,1};
int[] res = getsubArrSum(arrA,4);
for (int i = 0; i < res.length; i++) {
System.out.print(res[i]+" ");
}
System.out.println();
System.out.println("-----------");
int[] arrY={1,1,1,5,5,4};
int[] countsubArrY = CountOfdistinctsubArrY(arrY, 2);
for (int i = 0; i < countsubArrY.length; i++) {
System.out.print(countsubArrY[i]+" ");
}
System.out.println();
System.out.println("-----------");
int res1 = getRes(arrA, arrY);
System.out.println(res1);
}

/**
 * 暴力遍历每一个Index记录最大值
 * @param arrA
 * @param arrY
 * @return
 */
private static int getRes(int[] arrA,int[] arrY){
    int max=0;
    for (int i = 0; i < arrA.length; i++) {
        int[] resA=getsubArrSum(arrA,i);
        int[] counts=CountOfdistinctsubArrY(arrY,i);
        for (int j = 0; j <resA.length ; j++) {
            max=Math.max(max,resA[j]*counts[j]);
        }
    }
    return max;
}
/**
 * 记录以arrA[index]到最后   这个子数组中累加和
 * 如当arrA=[1,1,5,-7,4] ，index=0; -->返回的结果为：[1,2,7,0,4]
 * 如当arrA=[1,1,5,-7,4] ，index=1; -->返回的结果为：[1,6,-1,3]
 * @param arrA
 * @param index
 * @return
 */
private static int[] getsubArrSum(int[] arrA,int index){
    int[] res = new int[arrA.length - index];
    if(arrA==null||arrA.length==0){
        return res ;
    }
    for (int i = index; i < arrA.length ; i++) {
        if(i==index){
            res[0]=arrA[index];
        }else {
            res[i-index]=arrA[i]+res[i-index-1];
        }
    }
    return res;
}
/**
 * 记录以arrY[index]到最后这个子数组中  不重复个数的累加
 * 如arrY=[1,1,5,5,4],index=0时返回--->[1,1,2,2,3]
 * 如arrY=[1,1,5,5,4],index=1时返回--->[1,2,2,3]
 * @param arrY
 * @param index
 * @return
 */
private static int[] CountOfdistinctsubArrY(int[] arrY,int index){
    int[] res=new int[arrY.length-index];
    int[] countNums = new int[51];
    for (int i = index; i <arrY.length ; i++) {
        int count=0;
        countNums[arrY[i]]++;
        for (int j = 0; j <countNums.length ; j++) {
            if(countNums[j]>=1){
                count++;
            }
        }
        res[i-index]=count;
    }
    return res;
}

}