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.
Try to find the sum of values of elements larger than a_i in array 1..i for all i.
Try to solve problems where subarray starts at odd position first.
can you explain the idea for question 1 a bit more? I am not getting it. Thanks in advance.
Imagine you have a sorted array, what will happen if you add a number to this array?