Блог пользователя _Chaitanya1999

Автор _Chaitanya1999, история, 5 недель назад, По-английски

I recently encountered a problem which states : There is an array A which contains n integers. In one operation we can swap Ai with one of its neighbours i.e., swap(Ai,Ai+1) or swap(Ai,Ai-1) provided any element in the array can be swapped atmax once. After doing some optimal number of operations, we have to find the max value of summation of i*Ai for i = 1 to n.

For ex — A : [2,1,4,3] n = 4

Ans : 30 Swap elements at index 1,2 and elements at 3,4 that gives us the final array as [1,2,3,4]. The sum is 1*1 + 2*2 + 3*3 + 4*4 = 1+4+9+16 = 30

Can someone help me with the ideas to solve this problem ?

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор _Chaitanya1999, история, 4 года назад, По-английски

If you want to directly access the problem you can click here


Problem Statement You are given array a of n integers. You need to split the array into 2 arrays (one of which may be empty) such that sum of product of these 2 arrays is maximum. Formally, you need to find l such that sum of a1⋅a2⋅⋯⋅al and al+1⋅al+2⋅⋯⋅an is maximum over all valid choices for l. Note that an empty array has a product of 0.

Output Print the maximum sum of product of the arrays mod 1e9+7.

Constraints 1≤n≤1e5 , 1≤|ai|≤1e9
I tried to solve this problem by pre-calculating prefix product and suffix product modulo M(1e9+7) and taking the maximum among every i (1<=i<=n).But still its showing me WA for large inputs of a[i]. Can anyone suggest me where am I making a mistake ?
Thanks in Advance. 

Полный текст и комментарии »

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится