合唱团

学习了各位大佬的代码，使用两个一维矩阵的java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] val = new int[n];
        for (int i = 0; i < n; i ++) {
            val[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        int d = sc.nextInt();
        System.out.println(helper(val, n, k, d));
    }

    public static long helper(int[] val, int n, int k, int d){
        long maxdp[] = new long[n + 1];
        long mindp[] = new long[n + 1];
        Arrays.fill(maxdp, 1);
        Arrays.fill(mindp, 1);
        // 遍历待选取的第k~第1名学生
        for (int i = k - 1; i >= 0; i --) {
            // 第i名学生(1...i0...i1...n,i0<=j<=i1),j是第i名学生的下标，要求i的前面至少有i - 1个人
            // 则j>=i, 要求i的后面至少有k-i个人，则n-j>=k-i,j<=n-k+i
            for (int j = i; j <= n - k + i; j ++) {
                // 前一名学生(i+1)可以是当前学生下标往后延顺d个，m=[j+1, j+d]
                for (int m = j + 1; m <= j + d && m <=n; m ++) {
                    long temp1 = val[j] * maxdp[m];
                    long temp2 = val[j] * mindp[m];
                    maxdp[j] = Math.max(maxdp[j], Math.max(temp1, temp2));
                    mindp[j] = Math.min(mindp[j], Math.min(temp1, temp2));
                }
            }
        }
        long res = Long.MIN_VALUE;
        for (long x: maxdp) {
            res = Math.max(x, res);
        }
        return res;
    }
}

1. 看到这道题，首先最基本的想法一般是从n中抽取k个数，然后验证是否符合条件，复杂度大概是是一个非指数级可解问题
2. 接着进一步优化，首先可以发现因为限制了相对位置d,所以问题是位置相关的，而根据乘法交换率，计算时位置无关，因此保持其位置而不是考虑排序方法更好归纳问题。因此设人的序列为ListA:a1,a2,....,an
3. 这道题主要超变量有ListA,N.K,D从这道题跟具体的人选取与不选取有关，从头或从尾砍掉或选取一部分人，可以保持这个问题本身性质不变而只在超变量有改变，具有子问题的性质，且是最优化问题且包含最优子问题，因此考虑上贪心算法或者动态规划算法，并且先不考虑正负问题。
4. 贪心的2个要求是最优子问题和贪心选择（在子问题迭代过程每一步都是最佳，其中不会有其它选择优于我的选择【这也是很多贪心算法的证明】）考虑ListA中对an这个人的选择入k和抛弃，前面子问题会变成k-1或者k，显而易见直接丢掉算子问题不能保证最优，因此考虑动态规划。
5. 动态规划要求是最优子问题，重叠子问题，而动态规划又经常被大牛叫为打表算法，因此考虑打表，动态规划首先都要列出递推方程，考虑以砍尾部来划归子问题
6. （图里公式max的第一行d应该为大写D,其应该被重置）
7. 但是这样就会被列为三维矩阵，非常麻烦且不直观，考虑到距离d会因为选择了某人而重置为D所以考虑另外一种切分方法
8. 但是这种方法有个问题就是listA前面的后面可能会空一大截，不一定从尾巴或头部开始切，这也符合实际问题需要。于是表大概就长下面这个样子：
9. 这样就可以解决最大问题了，但是因为涉及正负数，负数最小的可能在下一次乘法中反成最大，所以得考虑打两个表，一个最小表一个最大表，判断哪个大取哪个。
   
10. 照这个思路的具体实现跟高赞答案一样

	
	

		import java.util.Scanner;
//主要参考@菜鸡华的代码
//kk dd one命名引起不适所以替换成简洁有力的命名K D i
//在N的遍历中使其终止与N-K+k，不进行剩下不必要的训练。
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            //读数据
            int N = sc.nextInt();

            int[] arr = new int[N + 1];

            for (int i = 1; i <= N; i++) {
                arr[i] = sc.nextInt();
            }

            int K = sc.nextInt();

            int D = sc.nextInt();

            
            //规划数组表示，使用两个数组保证，最大正数最小负数都有保存
            long[][] f = new long[N + 1][K + 1];//人直接对应坐标,n和K都要+1
            long[][] g = new long[N + 1][K + 1];
            //初始化k=1的情况
            for(int i = 1;i<=N;i++){
                f[i][1] = arr[i];
                g[i][1] = arr[i];
            }
            //自底向上递推
            for(int k=2;k<=K;k++){
                for(int i = k;i<=N-K+k;i++){
                    //求解当i和k定的时候，每步最优子问题   
                    long tempmax = Long.MIN_VALUE;
                    long tempmin = Long.MAX_VALUE;
                    for(int left = Math.max(k-1,i-D);left<=i-1;left++){
                        if(tempmax<Math.max(f[left][k-1]*arr[i],g[left][k-1]*arr[i])){
                            tempmax=Math.max(f[left][k-1]*arr[i],g[left][k-1]*arr[i]);
                        }
                        if(tempmin>Math.min(f[left][k-1]*arr[i],g[left][k-1]*arr[i])){
                            tempmin=Math.min(f[left][k-1]*arr[i],g[left][k-1]*arr[i]);
                        }
                    }
                    f[i][k] = tempmax;
                    g[i][k] = tempmin;
                }
            }
            //从最后一行选取最终最大值
            long result = Long.MIN_VALUE;
            for(int i = K;i<=N;i++){
                if(result<f[i][K]){
                    result = f[i][K];
                }
            }
            System.out.println(result);
        }
    }
} 
	

import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();          
            int[] array = new int [n+1];
            for (int i = 1; i <=n ; i++) {
                array[i] = sc.nextInt();
            }
            int K = sc.nextInt();           
            int d = sc.nextInt();            
            long[][] fmax = new long[K+1][n+1]; 
            long[][] fmin = new long[K+1][n+1]; 
            long  res = Integer.MIN_VALUE; 
            for (int i = 1; i <=n; i++) {
                fmax[1][i] = array[i];
                fmin[1][i] = array[i];
                for (int k = 2; k <=K; k++) {
                    for (int j = i-1 ; j > 0 &&  i-j<=d ; j--) {
                        fmax[k][i] = Math.max(fmax[k][i], Math.max(fmax[k-1][j] * array[i], fmin[k-1][j] * array[i]));
                        fmin[k][i] = Math.min(fmin[k][i], Math.min(fmax[k-1][j] * array[i], fmin[k-1][j] * array[i]));
                    }
                }
                res = Math.max(res ,fmax[K][i]);
            }
            System.out.println(res);
        }
        sc.close();
    }
}

package challenge;

import java.util.Scanner;

/**
 * @author Eden
 * @version 创建时间：2018年7月21日 下午6:25:29
 * @deprecated:
 *  题目描述
        有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学
        生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
    输入描述:
        每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来
        的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，
        k 和 d (1 <= k <= 10, 1 <= d <= 50)。
    输出描述:
        输出一行表示最大的乘积。
 */
public class Chorus {
    public static int[] arr;//学生能力数组
    public static long[][][] resultArr;//resultArr[学生个数][已选择学生个数][最大/最小]暂存在第count次选择时它的最大与最小值
    public static int k;
    public static int d;
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i]=input.nextInt();
        }
        k = input.nextInt();//选取学生个数
        d = input.nextInt();//编号相隔最大距离
        resultArr = new long[n][k+1][2];
        long[] result;
        long max=0;
        for(int i=0;i<n-k+1;i++){
            result = calculate(i,1);
            if(i==0)
                max=result[0];
            else
                if(result[0]>max)
                    max=result[0];
        }
        System.out.println(max);
    }
    
    public static long[] calculate(int index,int count){
        long[] result = {1,1};
        if(count>k){
            return result;
        }
        long max=arr[index],min=arr[index];
        //选择编号相隔有限制，rear表示已当前学生index为基准，能选择后面最大学生编号
        int rear = index+d+1;
        long firstTempResult,secondTempResult;
        if(rear>arr.length){
            rear=arr.length;
        }
        //递归求解
        for(int i=index+1;i<rear;i++){
            if(resultArr[i][count][0]==0&&resultArr[i][count][1]==0){
                firstTempResult = calculate(i,count+1)[0]*arr[index];
                secondTempResult = calculate(i,count+1)[1]*arr[index];
            }else{
                firstTempResult = resultArr[i][count][0]*arr[index];;
                secondTempResult = resultArr[i][count][1]*arr[index];
            }
            if(firstTempResult>max)
                max=firstTempResult;
            if(firstTempResult<min)
                min=firstTempResult;
            if(secondTempResult>max)
                max=secondTempResult;
            if(secondTempResult<min)
                min=secondTempResult;
        }
        result[0]=max;
        resultArr[index][count-1][0]=max;
        result[1]=min;
        resultArr[index][count-1][1]=min;
        //返回最大最小值
        return result;
    }
}

	

 public static void main(String[] args) {
    Scanner scanner  = new Scanner(System.in);
    String line = scanner.nextLine();
    int n = Integer.parseInt(line);

    line = scanner.nextLine();
    String[] s = line.split(" ");
    int arr[] = new int[n];
    for (int i = 0;i < n;i ++) {
        arr[i] = Integer.parseInt(s[i]);
    }

    line = scanner.nextLine();
    String []s1 = line.split(" ");
    int k = Integer.parseInt(s1[0]);
    int d = Integer.parseInt(s1[1]);
    dp(arr, k , d);
} 

public static void dp(int []arr, int k, int d) {
    //dp[i][j]表示以i为最后一个人的下标并且j为已选人数
    //由于有正有负，所以两个数组一个存最大值一个存最小值
    long [][]dpn = new long[arr.length][k + 1];
    long [][]dpm = new long[arr.length][k + 1];
    //以某个元素为结尾时的最大值
    long max = Integer.MIN_VALUE;
    for (int i = 0;i < arr.length;i ++) {
        dpn[i][1] = arr[i];
        dpm[i][1] = arr[i];
        //因为一共要选k个人，所以这里再做一个循环
        for (int kk = 2; kk <= k; kk ++) {
            for (int j = i - 1; j >= 0 && i - j <= d;j -- ) {
                //如果是正值，选大的
                dpm[i][kk] = Math.max(dpm[i][kk], Math.max(dpm[j][kk - 1] * arr[i], dpn[j][kk - 1] * arr[i]));
                //如果是负值，选小的
                dpn[i][kk] = Math.min(dpn[i][kk], Math.min(dpm[j][kk - 1] * arr[i], dpn[j][kk - 1] * arr[i]));
            }
        }
        max = Math.max(dpm[i][k], max);
    }
    System.out.println(max);
}

这个问题只要理解了从递归到动态规划的演变过程之后，就不难做出来了。

首先我们来看看递归的解题思路：

（cur：当前对象的下标，pre：上一次选择的对象的下标， count：已选择的人数，temp：当前乘积：result[0]：最终乘积）

对于n个人无非就是能不能选，以及选与不选的问题！

判断能不能选：需满足 cur - pre <= d

选与不选：就是递归的两个分支了

筛选结果：当count == k时，将当前乘积temp 与 最终乘积result[0] 择优存入result[0]中

递归出口：当cur >= n || count >= k时，由于筛选结果是在进入递归时的第一步操作，换言之，就是对上一次递归结果，进行筛选，所以当count==k时，已经可以返回了。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ability = new int[n];
        for (int i = 0; i < n; i++) {
            ability[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        int d = sc.nextInt();

        long maxProduct = getMaxProduct(ability, k, d);
        System.out.println(maxProduct);
        sc.close();
    }
private static long getMaxProduct2(int[] ability, int k, int d) {
    if (ability.length == 1) {
        return ability[0];
    }
    long[] result = { Long.MIN_VALUE };
    int count = 0;
    int pre = -1;
    int cur = 0;
    long temp = 1;
    process(ability, k, d, count, pre, cur, temp, result);
    return result[0];
}

/**
 * @param ability
 * @param k
 * @param d
 * @param count 表示已选人数
 * @param pre    表示上一次选择的人的下标
 * @param cur    表示当前的人的下标
 * @param temp  用于保存当前乘积
 * @param result 用于存储结果
 * @return
 */
private static void process(int[] ability, int k, int d, int count, int pre, int cur, long temp,
        long[] result) {
    if (count == k) {
        result[0] = Math.max(temp, result[0]);
    }
    if (cur >= ability.length || count >= k) {
        return;
    }
    //可选
    if (pre == -1 || cur - pre <= d) {
        //选
        process(ability, k, d, count + 1, cur, cur + 1, temp * ability[cur], result);
        //不选
        process(ability, k, d, count, pre, cur + 1, temp, result);
    }
}

接下来分析一下怎么由递归演变到动态规划：
由于乘积，我们很容易想到，需要保存最大值和最小值（因为最大值可以=负数min，也可以=正数max）
所以开辟两个空间maxProduct和minProduct，然后只需要将递归过程中使用到的变量保存起来维护就好了。
如：
cur：就是i
pre：也是i
count：是j
temp：就是两个数组的值了
解释一下maxProduct[i][j]的含义：（maxProduct[i][j]类似）

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ability = new int[n];
        for (int i = 0; i < n; i++) {
            ability[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        int d = sc.nextInt();

        long maxProduct = getMaxProduct(ability, k, d);
        System.out.println(maxProduct);
        sc.close();
    }

    private static long getMaxProduct(int[] ability, int k, int d) {
        long[][] maxProduct = new long[ability.length][k];
        long[][] minProduct = new long[ability.length][k];
        init(maxProduct, ability);
        init(minProduct, ability);

        for (int i = 1; i < ability.length; i++) {
            for (int j = 1; j < k; j++) {
                int start = i - d;
                start = start < 0 ? 0 : start;
                int end = i - 1;

                long maxTemp = getMaxFromMaxProduct(maxProduct, start, end, j - 1);
                long minTemp = getMinFromMinProduct(minProduct, start, end, j - 1);

                if (ability[i] == 0) {
                    maxProduct[i][j] = 0;
                    minProduct[i][j] = 0;
                }
                else if (ability[i] > 0) {
                    maxProduct[i][j] = ability[i] * maxTemp;
                    minProduct[i][j] = ability[i] * minTemp;
                }
                else {
                    maxProduct[i][j] = ability[i] * minTemp;
                    minProduct[i][j] = ability[i] * maxTemp;
                }
            }
        }
        long res = Long.MIN_VALUE;
        for (int i = 0; i < maxProduct.length; i++) {
            res = Math.max(res, maxProduct[i][k - 1]);
        }
        return res;
    }

    private static long getMinFromMinProduct(long[][] minProduct, int start, int end, int j) {
        long res = Long.MAX_VALUE;
        for (int i = start; i <= end; i++) {
            res = Math.min(minProduct[i][j], res);
        }
        return res;
    }

    private static long getMaxFromMaxProduct(long[][] maxProduct, int start, int end, int j) {
        long res = Long.MIN_VALUE;
        for (int i = start; i <= end; i++) {
            res = Math.max(maxProduct[i][j], res);
        }
        return res;
    }

    private static void init(long[][] arr, int[] ability) {
        for (int i = 0; i < arr.length; i++) {
            arr[i][0] = ability[i];
        }
        for (int j = 0; j < arr[0].length; j++) {
            arr[0][j] = ability[0];
        }
    }

这题可以从前递推，也可以从后递推，我选择的是从前递推的思路

import java.util.Scanner;

public class Main {
    // 参考 【小刀初试】的算法思想， Java版本，便于理解
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNextInt()) {
			int n = cin.nextInt(); 			// n 个学生
			int[] arr = new int [n+1];
			for (int i = 1; i <=n ; i++) {
				arr[i] = cin.nextInt();
			}
			int K = cin.nextInt();			  // 选出K个
			int d = cin.nextInt();			  // 两个学生的位置编号的差不超过 d
			long[][] fmax = new long[K+1][n+1]; // 记录最大乘积
			long[][] fmin = new long[K+1][n+1]; // 记录最小乘积
			// fmax[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；
			// fmin[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；
			//初始化第一行
			long  res = Integer.MIN_VALUE; // 记得用Long类型，考虑数值范围
			for (int i = 1; i <=n; i++) {
				fmax[1][i] = arr[i];
				fmin[1][i] = arr[i];
				for (int k = 2; k <=K; k++) {
					for (int j = i-1 ; j > 0 &&  i-j<=d ; j--) {
						fmax[k][i] = Math.max(fmax[k][i], Math.max(fmax[k-1][j] * arr[i], fmin[k-1][j] * arr[i]));
						fmin[k][i] = Math.min(fmin[k][i], Math.min(fmax[k-1][j] * arr[i], fmin[k-1][j] * arr[i]));
					}
				}
				res = Math.max(res ,fmax[K][i]);
			}
			System.out.println(res);
		}
	}
}