In this HackerRank Subsequence Weighting problem, you have given a sequence, output the maximum weight formed by an increasing subsequence.
Problem solution in Python programming.
#!/bin/python3
import os
import sys
import bisect
# Complete the solve function below.
def solve(a, w):
b = [[0,0],[10000000000,10000000000]]
for i in range(len(a)):
g = [a[i],w[i]]
bisect.insort(b,g)
ind = b.index(g)
if b[ind+1][0] != b[ind][0] and b[ind-1][0] != b[ind][0]:
b[ind][1]+=b[ind-1][1]
for j in range(ind+1,len(b)):
if b[j][1] >b[ind][1]:
break
b = b[:ind+1] + b[j:]
elif b[ind+1][0] == b[ind][0]:
b[ind][1]+=b[ind-1][1]
if b[ind+1][1]>=b[ind][1]:
b.remove(b[ind])
else:
b.remove(b[ind+1])
for j in range(ind+1,len(b)):
if b[j][1]>b[ind][1]:
break
b = b[: ind+1] + b[j: ]
elif b[ind-1][0] ==b[ind][0]:
b[ind][1] += b[ind-2][1]
if b[ind-1][1] >= b[ind][1]:
b.remove(b[ind])
else:
for j in range(ind+1,len(b)):
if b[j][1]>b[ind][1]:
break
b = b[: ind+1] + b[j: ]
b.remove(b[ind-1])
return b[-2][1]
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
for t_itr in range(t):
n = int(input())
a = list(map(int, input().rstrip().split()))
w = list(map(int, input().rstrip().split()))
result = solve(a, w)
fptr.write(str(result) + 'n')
fptr.close()
Problem solution in Java Programming.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
// Complete the solve function below.
static final int N = 200005;
static long[] max = new long[N];
static long getMax(int x) {
long maxw=0;
for(;x>0;x-=x&(-x)) maxw=Math.max(maxw, max[x]);
return maxw;
}
static void update(int x,long w) {
for(;x<N;x+=x&(-x)) max[x]=Math.max(max[x], w);
}
static long solve(int[] a, int[] w) {
int n = a.length;
TreeSet<Integer> ts = new TreeSet<>();
for(int i=0;i<N;i++) max[i]=0;
for(int i=0;i<n;i++){
ts.add(a[i]);
}
Iterator<Integer> it = ts.iterator();
HashMap<Integer, Integer> mp = new HashMap<>();
int m = 0;
while(it.hasNext()){
mp.put(it.next(),m++);
}
long ans=0;
for(int i=0;i<n;i++){
long maxw = getMax(mp.get(a[i]));
ans=Math.max(ans, maxw+(long)w[i]);
update(mp.get(a[i])+1, maxw+(long)w[i]);
}
return ans;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int tItr = 0; tItr < t; tItr++) {
int n = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
int[] a = new int[n];
String[] aItems = scanner.nextLine().split(" ");
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int aItr = 0; aItr < n; aItr++) {
int aItem = Integer.parseInt(aItems[aItr]);
a[aItr] = aItem;
}
int[] w = new int[n];
String[] wItems = scanner.nextLine().split(" ");
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int wItr = 0; wItr < n; wItr++) {
int wItem = Integer.parseInt(wItems[wItr]);
w[wItr] = wItem;
}
long result = solve(a, w);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
Problem solution in C++ programming.
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
using namespace std;
#define GI ({int new_input;scanf("%d",&new_input);new_input;})
typedef unsigned long long ll;
ll Tree[800000];
void updateTree(int b, int e, int p, ll val, int idx=1) {
if(p < b || p > e) return ;
if(p == b && p == e){
Tree[idx] = max(Tree[idx],val);
return ;
}
int mid = (b+e)/2;
int lt = (idx<<1);
int rt = ((idx<<1)+1);
updateTree(b, mid, p, val, lt);
updateTree(mid+1, e, p, val, rt);
Tree[idx] = max(Tree[lt], Tree[rt]);
return ;
}
ll query(int b,int e,int start,int end,int node){
if(e<start || b>end)return 0;
if(b<=start && e>=end)return Tree[node];
int mid=(start+end)>>1;
return max(query(b,e,start,mid,node*2),query(b,e,mid+1,end,node*2+1));
}
ll input[200000];
ll w[200000];
map<ll,int>m;
set<ll>s;
int main() {
int t=GI;
while(t--){
m.clear();s.clear();
s.empty();
memset(Tree,0,sizeof Tree);
int n=GI;
for(int i=0;i<n;i++){
scanf("%lld",&input[i]);
s.insert(input[i]);
}
for(int i=0;i<n;i++){
scanf("%lld",&w[i]);
}
int in=1;
set<ll>::iterator it;
for(it=s.begin();it!=s.end();it++){
m[*it]=in;
in++;
}in--;
ll ans=0;
for(int i=0;i<n;i++){
int mapped=m[input[i]];
if(mapped==1){
updateTree(1,in,mapped,w[i],1);
ans=max(ans,w[i]);
}
else{
ll get=query(1,mapped-1,1,in,1);
ans=max(ans,get+w[i]);
updateTree(1,in,mapped,w[i]+get,1);
}
}
cout<<ans<<endl;
}
return 0;
}
Problem solution in C programming.
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <stdlib.h>
long long a[1000000][4],b[1000000],w[1000000],q[1000000],t,i,j,k,l,m,n,nn;
long long makaj(long long ind, long long kto, long long vaha, long long lava)
{
long long hm;
if(a[ind][0] == a[ind][2])
{
if(vaha+lava > a[ind][3]) a[ind][3] = vaha+lava;
return a[ind][3];
}
if(kto<=a[ind][1])
{
hm = makaj(2*ind, kto, vaha, lava);
if(lava + vaha > hm) hm = lava+vaha;
if(hm > a[ind][3]) a[ind][3] = hm;
return a[ind][3];
}
else
{
if(a[2*ind][3]>lava) lava = a[2*ind][3];
hm = makaj(2*ind+1, kto, vaha, lava);
if(lava + vaha > hm) hm = lava+vaha;
if(hm > a[ind][3]) a[ind][3] = hm;
return a[ind][3];
}
return -100000000000LL;
}
void vytvaraj(long long ind,long long zac, long long kon)
{
long long hh;
hh = q[(zac+kon)/2];
a[ind][0] = q[zac];
a[ind][1] = hh;
a[ind][2] = q[kon];
a[ind][3] = 0;
if(zac==kon) return;
vytvaraj(2*ind,zac,(zac+kon)/2);
vytvaraj(2*ind+1,(zac+kon)/2+1,kon);
return;
}
int com(const void *x, const void *y)
{
if(*(long long*)x > *(long long*)y) return 1;
return -1;
}
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);;
for(i=0;i<n;i++) scanf("%lld",b+i);
for(i=0;i<n;i++) scanf("%lld",w+i);
for(i=0;i<n;i++) q[i]= b[i];
qsort(q,n,sizeof(q[0]),com);
nn=1;
for(i=1;i<n;i++) if(q[i]!=q[i-1]) q[nn++] = q[i];
vytvaraj(1,0,nn-1);
m=0;
for(i=0;i<n;i++)
{
makaj(1,b[i],w[i],0);
}
printf("%lldn",a[1][3]);
}
return 0;
}
