Question

In: Computer Science

A food fest is organised at the JLN stadium. The stalls from different states and cities...

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

Solutions

Expert Solution

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]);
    }
}

Related Solutions

Why are stars visible from the northern cities different from the stars that are visible in...
Why are stars visible from the northern cities different from the stars that are visible in southern cities?
Some states exclude necessities, such as food and clothing, from their sales tax. Other states do...
Some states exclude necessities, such as food and clothing, from their sales tax. Other states do not. Consider New York state, does it exclude necessities, why or why not? As with all things, one decision can lead to another. Once necessities are excluded, “necessities” must be defined. Research the tax definition of “necessity” in New York (or another if your state does not exclude) and evaluate it.
Some states exclude necessities, such as food and clothing, from their sales tax. Other states do...
Some states exclude necessities, such as food and clothing, from their sales tax. Other states do not. •Discuss the merits of this exclusion in terms of both efficiency and equity. •Consider North Carolina, does it exclude necessities, why or why not? •As with all things, one decision can lead to another. Once necessities are excluded, “necessities” must be defined. Research the tax definition of “necessity” in North Carolina (or another if your state does not exclude) and evaluate it.
Some states exclude necessities, such as food and clothing, from their sales tax. Other states do...
Some states exclude necessities, such as food and clothing, from their sales tax. Other states do not. • Discuss the merits of this exclusion in terms of both efficiency and equity. • Consider Texas your own home state, does it exclude necessities, why or why not? • As with all things, one decision can lead to another. Once necessities are excluded, “necessities” must be defined. Research the tax definition of “necessity” in your state (or another if your state does...
GMO labeling A genetically modified food is a food product developed from a different genetically modified...
GMO labeling A genetically modified food is a food product developed from a different genetically modified organism (GMO) such as a crop plant, animal or microorganisms. The general principle of producing a GMO is to add novel genetic material into an organism's genome resulting in both new and useful traits. Some governments (like the entire EU, China and Japan) have emphasized risks over benefits from GM foods and require mandatory labeling and traceability, while others, such as the U.S., have...
Cities, States, and Businesses Lead the Way to Reduce Greenhouse Gases Although the United States signed...
Cities, States, and Businesses Lead the Way to Reduce Greenhouse Gases Although the United States signed the original Kyoto Protocol, the U.S. Congress never ratified the agreement so the protocol has never been legally binding on the United States. The administration of President George W. Bush argued that there was no scientific consensus on global warming and that the costs of reducing greenhouse gases were simply too high. However, many state and local governments felt they had waited long enough...
A simple random sample of 101 cities and counties in the United States was selected and...
A simple random sample of 101 cities and counties in the United States was selected and the number of positive COVID-19 cases per 1000 citizens was recorded for each. The mean number of positive cases for this sample of 101 counties and cities was 253, with a standard deviation of 11.4. Due to a couple of cities with extremely high numbers of cases the distribution is skewed heavily to the right. If appropriate, use this information to calculate and interpret...
In many cities and towns across the United States, the numbering system of the roads is...
In many cities and towns across the United States, the numbering system of the roads is based on a grid, similar to the latitude and longitude lines on a globe. Suppose the green lines in the following graph represent two east-west and two north-south running roads in a Midwestern town. Write equations for the two horizontal and two vertical lines that represent roads in the town. 2. The Willis Tower (formerly known as the Sears Tower) in Chicago, Illinois, is...
Different types of cities emerge under different circumstances. For each of the following cases explain the...
Different types of cities emerge under different circumstances. For each of the following cases explain the axioms of urban economics and the economic market forces, which cause a city of a particular type to develop. Backyard production - no cities. Trading city. Factory city. Processing city Innovation city.
36 random samples of individuals from six different cities were asked how much time they had...
36 random samples of individuals from six different cities were asked how much time they had been spending per day watching TV. If it was found that the SSTr = 3153 and the SST = 11225, then fill out the table below (not all squares have blanks!). Whole numbered answers may be left as such, all else should be rounded to one decimal place. Source DF Sum of squares Mean squares F Pr > F Treatment 3153 MSTr 0.066 Error...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT