Cheapest Subarray

Problem:-

Visuals can be deceptive, and so can be the titles of the contest, but not every time you’ll be asked tough questions in an EASY contest.
In this problem, you will be given an array of integers and you need to tell the cost of the cheapest possible subarray of length at least two.
A subarray is the sequence of consecutive elements of the array and the cost of a subarray is the sum of minimum and the maximum value in the subarray.
Note: In an array of length 

n

, there are 

n(n1)2

 subarrays whose length is atleast 2.
Constraints:


  • 1t10


  • 2n2×104


  • 1ai2×104

Input Format:
The first line contains a single integer 

t

  denoting the number of test cases.
The first line of each test case contains 

n

  i.e the number of elements in the array. Next lines contains 

n

  space-separated integers 

ai


Output Format:
Print 

t

 lines each containing a single integer. 

ith

 integer denotes the cost of the cheapest subarray for the 

ith

 array.

SAMPLE INPUT
 
2
2
3 2
3
3 4 2
SAMPLE OUTPUT
 
5
6
Explanation

  • The only possible subarray of length atleast 2 is [3, 2], Its cost is minimum + maximum = 2 + 3 = 5;
  • Three subarrays of lengths at least 2 are possible i.e. [3, 4], [4, 2] and [3, 4, 2]. The minimum possible cost is 6 for the subarrays [4, 2] and [3, 4, 2]
Time Limit:1.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB

solution:-

#include<stdio.h>
void main()
{
     int t,n,a[100000],,i,j,sum,min;
     scanf(“%d”,&t);
     for(j=0;j<=t1;j++)
     {
        scanf(“%d”,&n);
        for(i=0;i<=n1;i++)
         scanf(“%d”,&a[i]);
        for(i=0;i<=n2;i++)
        {
            sum=a[i]+a[i+1];
b[i]=sum;
        }
        min=b[0];
        for(i=0;i<=n2;i++)
        {
            if(min>b[i])
            {
                min=b[i];
            }
        }
        printf(“%dn”,min);
     }
}

Leave a Reply

Your email address will not be published.