riddle279's blog

By riddle279, history, 3 years ago, In English

I have come across two problems but could not build the logic to implement them.

Question 1:

given an array a of n elements [a1,a2,a3,...,an]. To calculate f(i) first sorting elements from 1 to i in non-decreasing order, then use the formula f(i)= =(1*a[1])+(2*a[2])+(3*a[3])+..+(i*a[i]). Compute (f(1)+f(2)+f(3)+...+f(n))mod(10^9+7).

constraints: 1<=n<=10^5

1<=a[i]<=10^6

Sample case: a[]=[4,3,2,1] output:65

explanation:

f(1)=1*4=4 f(2)=1*3+2*4=11 f(3)=1*2+2*3+3*4=20 f(4)=1*1+2*2+3*3+4*4=30

so output is 65%(10^9+7)=65.

Question 2:

Given an array a of n elements [a0,a1,a2,...an-1]. The value of array is defined square of sum of even positioned elements minus odd positioned elements. Find the maximum possible value of any subarray of a[].

constraints: 1<=n<=10^5

-10^6<=a[i]<=10^6

sample case: a[]=[-1,-4,2] output: 36

explanation: consider the subarray[-4,2] the value is(-4-2)^2=36.

  • Vote: I like it
  • -7
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Try to find the sum of values of elements larger than a_i in array 1..i for all i.

  2. Try to solve problems where subarray starts at odd position first.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain the idea for question 1 a bit more? I am not getting it. Thanks in advance.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Imagine you have a sorted array, what will happen if you add a number to this array?