304 North Cardinal St.
Dorchester Center, MA 02124

# Kth Max Subarray CodeChef Solution

## Kth Max Subarray CodeChef Solution in C++14

``````#include <bits/stdc++.h>
using namespace std;
#ifdef Azizul
#include "debug.cpp"
#else
#define dbg(x...)
#endif
#define   int  long long
#define   ld   long double
#define   pb   push_back
#define   vi   vector<int>
#define   bitcount(x)  (int)__builtin_popcount(x)
#define   Lsb(x)  (int)__builtin_ctzll(x)
#define   fast  ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define   sz(x)  (int)x.size()
#define   all(a) (a).begin(),(a).end()
#define   Yes  cout << "YES\n"
#define   No  cout << "NO\n"
#define   ff   first
#define   ss   second
#define   endl  "\n"
#define   pi   acos(-1.0)
#define   pii  pair<int,int>
#define   lcm(a,b) (a/__gcd(a, b)*b)

const int  mod = 998244353 ;
const int M = 200005 ;
const int inf = 1LL<<40 ;
vector <int> ans, a(M) ;
int n, m;

inline void solve() {
int n, m;
cin >> n >> m ;
vector <int> a(n+5) ;
for (int i=1;i<=n;++i) cin >> a[i] ;
vector <int> l(n+5), r(n+5) ;
stack <int> s;
s.push(0) ;
a[0] = a[n+1] = inf ;
for (int i=1;i<=n;++i) {
while (a[s.top()] <= a[i]) s.pop() ;
l[i] = i-s.top() ;
s.push(i) ;
}
while (!s.empty()) s.pop() ;
s.push(n+1) ;
for (int i=n;i>=1;i--) {
while (a[s.top()] < a[i]) s.pop() ;
r[i] = s.top()-i ;
s.push(i) ;
}
vector <pii> v;
for (int i=1;i<=n;++i) {
int ll = l[i], rr = r[i];
v.push_back({a[i], ll*rr}) ;
}
sort(all(v), greater<pii>()) ;
vector <int> pref(n) ;
for (int i=0;i<n;++i) {
pref[i] = v[i].ss ;
if (i > 0) pref[i] += pref[i-1] ;
}
while (m--) {
int x; cin >> x ;
int l = 0, r = n-1, ans ;
while (l <= r) {
int m = (l+r)>>1;
if (pref[m] >= x) {
ans = v[m].ff ;
r = m-1;
}
else l = m+1 ;
}
cout << ans << endl;
}
}
signed main()
{
fast ;
int t = 1 ;  cin >> t ;
while (t--) solve() ;
return 0 ;
}  ``````

## Kth Max Subarray CodeChef Solution in PYTH 3

``````# cook your dish here
#!/usr/local/bin/python3
import sys

def _l(x,y):
return x < y

def _le(x,y):
return x <= y

def biggest_prev(a,rng,start,fn):
st = [] # monotonically decreasing stack
ret = [0]*len(a)
for i in rng:
el = a[i]
while (st and fn(a[st[-1]],el)):
st.pop()
if st:
ans = abs(i - st[-1])
else:
ans = abs(i - start)
ret[i] = ans
st.append(i)
return ret

def solve():
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = biggest_prev(a,range(0,n),-1,_l)
c = biggest_prev(a,range(n-1,-1,-1),n,_le)
#print(list(zip(a,b,c)))
d = [[x,y*z] for (x,y,z) in zip(a,b,c)]
d.sort(key=lambda x: -x[0])
for i in range(1,len(d)):
d[i][1] += d[i-1][1]

#print(d)

for _ in range(m):
k = int(input())
ans = 0
if k <= d[0][1]:
ans = d[0][0]
else:
l, r = 0, n
while l < r-1:
mid = (l+r)//2
if d[mid][1] < k:
l = mid
else:
r = mid
ans = d[l+1][0]
print(ans)

def main():
for _ in range(int(input())):
solve()

main()``````

## Kth Max Subarray CodeChef Solution in C

``````#include <stdio.h>
#include <stdlib.h>

#define N	100000

struct A {
int i, a;
long long k;
} aa[N];

int compare(const void *a, const void *b) {
struct A *pa = (struct A *) a;
struct A *pb = (struct A *) b;

return pa->a - pb->a;
}

int binsearch(struct A *aa, int n, long long x) {
int l = -1, r = n - 1;

while (r - l > 1) {
int m = (l + r) / 2;

if (aa[m].k >= x)
r = m;
else
l = m;
}
return r;
}

int ll[N], dsu[N], used[N];

int find(int x) {
return dsu[x] < 0 ? x : (dsu[x] = find(dsu[x]));
}

void join(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return;
if (dsu[x] < dsu[y])
dsu[y] = x;
else if (dsu[x] > dsu[y])
dsu[x] = y;
else {
dsu[x]--;
dsu[y] = x;
}
}

long long count(int l) {
return (long long) l * (l + 1) / 2;
}

long long join_(int x, int y) {
int lx, ly, l;

x = find(x);
y = find(y);
lx = ll[x];
ly = ll[y];
l = ll[x] = ll[y] = (ll[x] + ll[y]);
join(x, y);
return count(l) - count(lx) - count(ly);
}

int main() {
int t;

scanf("%d", &t);
while (t-- > 0) {
int i, n, m;
long long k, cnt;

scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%d", &aa[i].a);
aa[i].i = i;
}
qsort(aa, n, sizeof(*aa), compare);
for (i = 0; i < n; i++) {
dsu[i] = -1;
ll[i] = 0;
}
k = 0;
for (i = 0; i < n; i++) {
int j = aa[i].i;

k += 1;
ll[j] = 1;
if (j - 1 >= 0 && ll[j - 1] > 0)
k += join_(j, j - 1);
if (j + 1 < n && ll[j + 1] > 0)
k += join_(j, j + 1);
aa[i].k = k;
}
cnt = count(n);
while (m-- > 0) {
long long p;

scanf("%lld", &p);
i = binsearch(aa, n, cnt - p + 1);
printf("%d\n", aa[i].a);
}
}
return 0;
}``````

## Kth Max Subarray CodeChef Solution in JAVA

``````/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;

{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}

public Reader(String file_name) throws IOException
{
din = new DataInputStream(
new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}

public String readLine() throws IOException
{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') {
if (cnt != 0) {
break;
}
else {
continue;
}
}
buf[cnt++] = (byte)c;
}
return new String(buf, 0, cnt);
}

public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ') {
}
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');

if (neg)
return -ret;
return ret;
}

public long nextLong() throws IOException
{
long ret = 0;
byte c = read();
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}

public double nextDouble() throws IOException
{
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
boolean neg = (c == '-');
if (neg)

do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');

if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}

if (neg)
return -ret;
return ret;
}

private void fillBuffer() throws IOException
{
BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}

private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}

public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
static boolean check(int x , int arr[] , int l[] , int r[]
, long k)
{
long tot = 0;
for(int i = 0; i < arr.length ; i++)
{
if(arr[i] >= x)
{
tot += (long)(r[i]-i+1)*(long)(i-l[i]+1);
}
}
// System.out.println(tot + " " + k);
if(tot >= k)
return true;

return false;
}
public static void main (String[] args) throws java.lang.Exception
{
int t = sc.nextInt();

StringBuffer str = new StringBuffer("");

while(t-- > 0)
{
int n = sc.nextInt();
int m = sc.nextInt();

int tmp[] = new int[n];
int arr[] = new int[n];
for(int i = 0 ; i < n ; i++)
{
arr[i] = sc.nextInt();
tmp[i] = arr[i];
}
Arrays.sort(tmp);

int l[] = new int[n];
int r[] = new int[n];

Stack<Integer> st = new Stack<Integer>();
for(int i = 0 ; i < n ; i++)
{
while(st.size() > 0 && arr[st.peek()] <= arr[i])
{
r[st.pop()] = i-1;
}
st.push(i);
}

while(st.size() > 0)
{
r[st.pop()] = n-1;
}

for(int i = n-1 ; i >= 0 ; i--)
{
while(st.size() > 0 && arr[st.peek()] < arr[i])
{
l[st.pop()] = i+1;
}
st.push(i);
}

while(st.size() > 0)
{
l[st.pop()] = 0;
}

HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

for(int i = 0 ; i < n ; i++)
{
map.put(tmp[i],i);
}
ArrayList<Integer> ls[] = new ArrayList[n];
for(int i = 0 ; i < n ; i++)
{
ls[i] = new ArrayList<Integer>();
}

for(int i = 0 ; i < n ; i++)
{
}
TreeMap<Long,Integer> mp = new TreeMap<Long,Integer>();
long tot = 0;
for(int i = n-1 ; i >= 0 ; i--)
{
for(Integer j : ls[i])
{
tot += (long)(j-l[j]+1)*(long)(r[j]-j+1);
}
mp.put(tot,tmp[i]);;
}
while(m-- > 0)
{
long k = sc.nextLong();

str.append(mp.get(mp.higherKey(k-1)));
str.append(System.lineSeparator());
}

}
System.out.println(str);
}
}``````

## Kth Max Subarray CodeChef Solution in PYPY 3

``````#!/usr/local/bin/python3
import sys

def _l(x,y):
return x < y

def _le(x,y):
return x <= y

def biggest_prev(a,rng,start,fn):
st = [] # monotonically decreasing stack
ret = [0]*len(a)
for i in rng:
el = a[i]
while (st and fn(a[st[-1]],el)):
st.pop()
if st:
ans = abs(i - st[-1])
else:
ans = abs(i - start)
ret[i] = ans
st.append(i)
return ret

def solve():
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = biggest_prev(a,range(0,n),-1,_l)
c = biggest_prev(a,range(n-1,-1,-1),n,_le)
#print(list(zip(a,b,c)))
d = [[x,y*z] for (x,y,z) in zip(a,b,c)]
d.sort(key=lambda x: -x[0])
for i in range(1,len(d)):
d[i][1] += d[i-1][1]

#print(d)

for _ in range(m):
k = int(input())
ans = 0
if k <= d[0][1]:
ans = d[0][0]
else:
l, r = 0, n
while l < r-1:
mid = (l+r)//2
if d[mid][1] < k:
l = mid
else:
r = mid
ans = d[l+1][0]
print(ans)

def main():
for _ in range(int(input())):
solve()

main()``````

## Kth Max Subarray CodeChef Solution in PYTH

``````import bisect

def right(arr, n):

st = [0]*n
a = [0]*n
index = 0
for i in xrange(1, n):
while (index >= 0 and arr[i] > arr[st[index]]):
index -= 1

a[i] = i if index < 0 else (i - st[index] - 1)
index += 1
st[index] = i

return a

def left(arr1, n):

arr = [0]*n
for i in xrange(n):
arr[i] = arr1[n - i - 1]

st = [0]*n
a = [1]*n
index = 0
for i in xrange(1, n):
while (index >= 0 and arr[i] >= arr[st[index]]):
index -= 1

a[i] = i + 1 if index < 0 else (i - st[index])
index += 1
st[index] = i

a.reverse()
return a

# def left(arr, n):
#
#     st = [0]*n
#     a = [1]*n
#     index = 0
#     st[0] = n - 1
#     for i in xrange(n - 2, -1 , -1):
#         while (index >= 0 and arr[i] >= arr[st[index]]):
#             index -= 1
#
#         a[i] = i + 1 if index < 0 else (i - st[index])
#         index += 1
#         st[index] = i
#
#     a.reverse()
#     return a

tt = int(raw_input())
for i in xrange(tt):
n, m = map(int, raw_input().split())
num = map(int, raw_input().split())
query = []
for j in xrange(m):
query.append(int(raw_input()))

rig = right(num, n)
lef = left(num, n)
temp = [0]*n
for j in xrange(n):
temp[j] = lef[j]*rig[j] + lef[j]

# print temp
ab = zip(num, temp)
ab.sort(reverse = True)
# num, temp = zip(*reversed(sorted(zip(num, temp))))
num, temp = zip(*ab)
accumulate = [0]*n
accumulate[0] = temp[0]
for j in xrange(1, n):
accumulate[j] = accumulate[j-1] + temp[j]

# print num, temp, accumulate
for j in xrange(m):
print num[bisect.bisect_left(accumulate, query[j])]``````
##### Kth Max Subarray CodeChef Solution Review:

In our experience, we suggest you solve this Kth Max Subarray CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Kth Max Subarray CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Kth Max Subarray CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!