In: Computer Science
A food fest is organised at the JLN stadium. The stalls from
different states and cities have been set up. To make the fest more
interesting, multiple games have been arranged which can be played
by the people to win the food vouchers. One such game to win the
food vouchers is described below:There are N number of boxes
arranged in a single queue. Each box has an integer I written on
it. From the given queue, the participant has to select two
contiguous subsequences A and B of the same size. The selected
subsequences should be such that the summation of the product of
the boxes should be maximum. The product is not calculated normally
though. To make the game interesting, the first box of subsequence
A is to be multiplied by the last box of subsequence B. The second
box of subsequence A is to be multiplied by the second last box of
subsequence B and so on. All the products thus obtained are then
added together.
If the participant is able to find the correct such maximum
summation, he/she will win the game and will be awarded the food
voucher of the same value.
Note: The subsequences A and B should be disjoint.
Example:
Number of boxes, N = 8
The order of the boxes is provided below:
Subsequence A
Subsequence B
The product of the subsequences will be calculated as below:
P1 = 9 * 8 = 72
P2 = 2 * 7 = 14
P3 = 3 * 6 = 18
Summation, S = P1 + P2 + P3 = 72 + 14 + 18 = 104
This is the maximum summation possible as per the requirement for
the given N boxes.
Tamanna is also in the fest and wants to play this game. She needs
help in winning the game and is asking for your help. Can you help
her in winning the food vouchers?
Input Format
The first line of input consists of the number of boxes, N.
The second line of input consists of N space-separated
integers.
Constraints
1< N <=3000
-106 <= I <=106
Output Format
Print the maximum summation of the product of the boxes in a
separate line.
Sample TestCase 1
Input
8
1 9 2 3 0 6 7 8
Output
104
Explanation
As explained in the example above.
Time Limit(X):
0.50 Sec(S) For Each Input.
Memory Limit:
512 MB
Source Limit:
100 KB
Below code is in Java. I hope it helps!
import java.util.Scanner;
import java.util.*;
public class Main {
static class pair {
int first, second;
public pair(int first, int second) {
this.first = first;
this.second = second;
}
}
static int getSubarraySum(int sum[], int i, int j) {
if (i == 0)
return sum[j];
else
return (sum[j] - sum[i - 1]);
}
static int maximumSumTwoNonOverlappingSubarray(int arr[], int N,
int K) {
int l = 0, m = 0;
int a1[] = new int[N / 2];
int a2[] = new int[N / 2];
int prod = 0;
int[] sum = new int[N];
sum[0] = arr[0];
for (int i = 1; i < N; i++)
sum[i] = sum[i - 1] + arr[i];
pair resIndex = new pair(N - 2 * K, N - K);
int maxSum2Subarray =
getSubarraySum(sum, N - 2 * K, N - K - 1)
+ getSubarraySum(sum, N - K, N - 1);
pair secondSubarrayMax =
new pair(N - K, getSubarraySum(sum, N - K, N - 1));
for (int i = N - 2 * K - 1; i >= 0; i--) {
int cur = getSubarraySum(sum, i + K, i + 2 * K - 1);
if (cur >= secondSubarrayMax.second)
secondSubarrayMax = new pair(i + K, cur);
cur = getSubarraySum(sum, i, i + K - 1)
+ secondSubarrayMax.second;
if (cur >= maxSum2Subarray) {
maxSum2Subarray = cur;
resIndex = new pair(i, secondSubarrayMax.first);
}
}
for (int i = resIndex.first; i < resIndex.first + K; i++) {
a1[l] = arr[i];
l++;
}
for (int i = resIndex.second; i < resIndex.second + K; i++) {
a2[m] = arr[i];
m++;
}
for (int i = 0; i < m; i++) {
if (a1[i] != 0 || a2[i] != 0) {
prod = prod + a1[i] * a2[m - (i + 1)];
}
}
return prod;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int k = 0;
int arr[] = new int[a];
for (int i = 0; i < a; i++) {
arr[i] = sc.nextInt();
}
int l = arr.length;
int ar[] = new int[a / 2];
for (int i = 1; i <= a / 2; i++) {
ar[k] = maximumSumTwoNonOverlappingSubarray(arr, l, i);
k++;
}
Arrays.sort(ar);
System.out.println(ar[k - 1]);
}
}