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

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

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.

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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