There are n students standing in a row, each student has a capability value. Niu Niu wants to select k students from the n students in order. He asks that the difference between the location numbers of the two adjacent students should not exceed d, so that the product of the ability values of the K students is the largest. Can you return to the maximum product?
Input Description:
Each input contains one test case. The first line of each test data contains an integer n (1 <= n <== 50), representing the number of students, and the next line contains n integers, representing each student's ability value ai in sequence (-50 <= ai <= 50). The next line contains two integers, k and D (1 <= k <= 10, 1 <= D <= 50).
Output description:
The output line represents the largest product.
Example 1
input
3
7 4 7
2 50
output
49
Analysis: First of all, this is an optimization problem [because the k students chosen are different, and the final results are different, so the biggest one needs to be chosen from these structures if the title is the most demanding one].
So we can first determine all the possible locations for choosing the k th student, get the maximum product of all the possible locations, and then choose the largest one from these maximum products.
So how do you determine all the possible locations for the k th student?
As long as we make sure that there are at least k-1 students to choose from after, the remaining places are all possible places for the k-th student.
How to solve it: Calculate the maximum product of selecting k-1 person, then multiply the ability value of the current k-th student, and get the maximum product of selecting K students.
So how do we determine all possible locations for k-1 students?
Here are two points to note:
1. Make sure that at least k-2 students can choose from the right to the right.
2. The number difference between the k-1 student and the K student does not exceed d.
At this time, there is another problem worthy of attention: students'ability values are positive and negative, then
When the ability value of the k-th student is positive, the maximum product of the k-th student can be obtained directly by multiplying the maximum product of the k-1 student by the ability value of the k-th student.
When choosing the maximum product of K students, we need to pay attention to multiplying the minimum product of k-1 students by the ability value of K students when the ability value of K students is negative, because the less negative, the greater the ability value of K students.
The students'ability array is arr[n+1], and the ability value of the first student is arr[i].
Dynamic programming is used to solve:
Definition state: f[one][k]: The maximum product of selecting K individuals from n individuals, where one represents the position of the K individuals [the last person selected], and K represents the position of the K individuals including this person, with a total of K individuals.
g[one][k]: The smallest product of selecting K individuals from n individuals, where one represents the position of the K individuals [the last person selected], and K indicates that there are k individuals including this person.
State transition equation: f[one][k] = max(f[one][k], max(f[left][k-1]*arr[one], g[left][k-1]*arr[one])
g[one][k] = min(f[one][k]，min(f[left][k-1]*arr[one]，g[left][k-1]*arr[one]))
Initial state: f[one][1]=g[one][1]=arr[one], one from 1 to n means that when a student is selected, the current maximum/minimum product is the student's ability value.
Return result: max(f[one][k]) one from K to n
import java.util.Scanner;
public class Chorus {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
//Total number
int n = sc.nextInt();
//Array of student ability values, the first person directly corresponds to arr[i]
int[] arr = new int[n + 1];
//Initialization
for (int i = 1; i <= n; i++) {//Human Direct Correspondence Coordinates
arr[i] = sc.nextInt();
}
//Number of students selected
int kk = sc.nextInt();
//spacing
int dd = sc.nextInt();
output(n,arr,kk,dd);
}
}
private static void output(int n, int[] arr, int kk, int dd) {
/*
* When recurrence occurs, it is expressed in the form of f[one][k]
* Among them: one represents the position of the last person, k includes this person, a total of k individuals
* The relationship between the original problem and the sub-problem: f[one][k]=max{f[left][k-1]*arr[one],g[left][k-1]*arr[one]}
*/
//Planning array
long[][] f = new long[n + 1][kk + 1];//Man directly corresponds to coordinates, n and kk all have + 1
long[][] g = new long[n + 1][kk + 1];
//Initialization k=1
for (int one = 1; one <= n; one++) {
f[one][1] = arr[one];
g[one][1] = arr[one];
}
//Bottom-up recursion
for (int k = 2; k <= kk; k++) {
for (int one = k; one <= n; one++) { //When selecting k individuals, all possible positions of k individuals
f[one][k] = Long.MIN_VALUE;
g[one][k] = Long.MAX_VALUE;
for (int left = Math.max(k - 1, one - dd); left <= one - 1; left++) { //All possible locations of the k-1 person [both to ensure that the interval satisfies the conditions and to ensure that there are k-2 persons in front of the k-1 person]
f[one][k] = Math.max(f[one][k], Math.max(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one]));
g[one][k] = Math.min(g[one][k], Math.min(f[left][k - 1] * arr[one], g[left][k - 1] * arr[one]));
}
//When the third for cycle is completed, the maximum/minimum product can be determined when the position of the k-th person is one [one traverses from K to n], and the k-th person [k traverses from 2 to kk] is selected altogether.
//Next time we need to determine the maximum product of selecting k+1 person, we only need to determine all possible positions of k+1 person (also expressed as one, one traverses from k+1 to n).
// Then, after determining all possible positions of k-2 persons, by calculating the product of the maximum/minimum product of these positions and arr[one], the maximum/minimum product for selecting k+1 persons with one position is determined.
}
}
/*
* kk=3 dd=2
* arr={0, -10, -20, -30, -40};
* f[1][1]=-10,f[2][1]=-20,f[3][1]=-30,f[4][1]=-40
* g[1][1]=-10,g[2][1]=-20,g[3][1]=-30,g[4][1]=-40
*
* k=2:
* one: 2~4
* one:2
* f[2][2]=Long.MIN_VALUE
* g[2][2]=Long.MAX_VALUE
* left: 1~1
* left:1
* f[2][2]=max(Long.MIN_VALUE,max(f[1][1]*arr[2],g[1][1]*arr[2]))=max(Long.MIN_VALUE,max(-10*-20,-10*-20))=max(Long.MIN_VALUE,200)=200
* g[2][2]=min(Long.MAX_VALUE,min(g[1][1]*arr[2],g[1][1]*arr[2]))=min(Long.MAX_VALUE,min(-10*-20,-10*-20))=min(Long.MIN_VALUE,200)=200
* one:3
* f[3][2]=Long.MIN_VALUE
* g[3][2]=Long.MAX_VALUE
* left:1~2
* left:1
* f[3][2]=max(Long.MIN_VALUE,max(f[1][1]*arr[3],g[1][1]*arr[3]))=max(Long.MIN_VALUE,max(-10*-30,-10*-30))=300
* g[3][2]=min(Long.MAX_VALUE,min(f[1][1]*arr[3],g[1][1]*arr[3]))=min(Long.MAX_VALUE,min(-10*-30,-10*-30))=300
* left:2
* f[3][2]=max(f[3][2],max(f[2][1]*arr[3],g[2][1]*arr[3]))=max(300,max(-20*-30,-20*-30))=600
* g[3][2]=min(g[3][2],min(f[2][1]*arr[3],g[2][1]*arr[3]))=min(300,min(-20*-30,-20*-30))=600
* one:4
* f[4][2]=Long.MIN_VALUE
* g[4][2]=Long.MAX_VALUE
* left: 2~3
* left:2
* f[4][2]=max(Long.MIN_VALUE,max(f[2][1]*arr[4],g[2][1]*arr[4]))=max(Long.MIN_VALUE,max(-20*-40,-20*-40))=800
* g[4][2]=min(Long.MAX_VALUE,min(f[2][1]*arr[4],g[2][1]*arr[4]))=min(Long.MIN_VALUE,min(-20*-40,-20*-40))=800
* left:3
* f[4][2]=max(f[4][2],max(f[3][1]*arr[4],g[3][1]*arr[4]))=max(800,max(-30*-40,-30*-40))=1200
* g[4][2]=min(g[4][2],min(f[3][1]*arr[4],g[3][1]*arr[4]))=min(800,min(-30*-40,-30*-40))=1200
* one:5
* f[5][2]=Long.MIN_VALUE
* g[5][2]=Long.MAX_VALUE
* left: 3~4
* left:3
* f[5][2]=
* g[5][2]=
* left:4
* f[5][2]=
* g[5][2]=
* k=3:
* one:3~4
* one:3
* f[3][3]=Long.MIN_VALUE
* g[3][3]=Long.MAX_VALUE
* left:2~2
* f[3][3]=max(Long.MIN_VALUE,max(f[2][2]*arr[3],g[2][2]*arr[3]))=max(Long.MIN_VALUE,max(200*-30,200*-30))=-6000
* g[3][3]=min(Long.MAX_VALUE,min(f[2][2]*arr[3],g[2][2]*arr[3]))=min(Long.MAX_VALUE,min(200*-30,200*-30))=-6000
* one:4
* f[4][3]=Long.MIN_VALUE
* g[4][3]=Long.MAX_VALUE
* left:2~3
* left:2
* f[4][3]=max(Long.MIN_VALUE,max(f[2][2]*arr[4],g[2][2]*arr[4]))=max(Long.MIN_VALUE,max(200*-40,200*-40))=-8000
* f[4][3]=min(Long.MAX_VALUE,min(f[2][2]*arr[4],g[2][2]*arr[4]))=min(Long.MAX_VALUE,min(200*-40,200*-40))=-8000
* left:3
* f[4][3]=max(f[4][3],max(f[3][2]*arr[4],g[3][2]*arr[4]))=max(f[4][3],max(600*-40,600*-40))=-24000
* g[4][3]=min(g[4][3],min(f[3][2]*arr[4],g[3][2]*arr[4]))=min(f[4][3],min(600*-40,600*-40))=-24000
*
* */
//After calculating the maximum product of all possible positions of the kth person, it is only necessary to select the maximum product of all possible positions of the kth person.
long result = Long.MIN_VALUE;
for (int one = kk; one <= n; one++) {
if (result < f[one][kk]) {
result = f[one][kk];
}
}
System.out.println(result);
}
}