Header Ads Widget

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<=t-1;j++)
     {
        scanf("%d",&n);
        for(i=0;i<=n-1;i++)
         scanf("%d",&a[i]);
        for(i=0;i<=n-2;i++)
        {
            sum=a[i]+a[i+1];
b[i]=sum;
        }
        min=b[0];
        for(i=0;i<=n-2;i++)
        {
            if(min>b[i])
            {
                min=b[i];
            }
        }
        printf("%d\n",min);
     }
}

Post a Comment

0 Comments