Algorithm


Problem Name: Data Structures - Subsequence Weighting

Problem Link: https://www.hackerrank.com/challenges/subsequence-weighting/problem?isFullScreen=true

In this HackerRank in Data Structures - Subsequence Weighting solutions

A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. 

You are given a sequence A in which every element is a pair of integers  i.e  A = [(a1, w1), (a2, w2),..., (aN, wN)].

For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : 

  • We call it increasing if for every i (1 <= i < M ) , bi < bi+1.
  • Weight(B) = v1 + v2 + ... + vM.

Task:
Given a sequence, output the maximum weight formed by an increasing subsequence.

Input:
The first line of input contains a single integer T. T test-cases follow. The first line of each test-case contains an integer N. The next line contains a1, a2 ,... , aN separated by a single space. The next line contains w1, w2, ..., wN separated by a single space.

Output:
For each test-case output a single integer: The maximum weight of increasing subsequences of the given sequence.

Constraints:
1 <= T <= 5
1 <= N <= 150000
1 <= ai <= 109, where i ∈ [1..N]
1 <= wi <= 109, where i ∈ [1..N]

Sample Input:

2  
4  
1 2 3 4  
10 20 30 40  
8  
1 2 3 4 1 2 3 4  
10 20 30 40 15 15 15 50

Sample Output:

100  
110

Explanation:
In the first sequence, the maximum size increasing subsequence is 4, and there's only one of them. We choose B = [(1, 10), (2, 20), (3, 30), (4, 40)], and we have Weight(B) = 100.

In the second sequence, the maximum size increasing subsequence is still 4, but there are now 5 possible subsequences:

1 2 3 4  
10 20 30 40

1 2 3 4  
10 20 30 50

1 2 3 4  
10 20 15 50

1 2 3 4  
10 15 15 50

1 2 3 4  
15 15 15 50

Of those, the one with the greatest weight is B = [(1, 10), (2, 20), (3, 30), (4, 50)], with Weight(B) = 110.

Please note that this is not the maximum weight generated from picking the highest value element of each index. That value, 115, comes from [(1, 15), (2, 20), (3, 30), (4, 50)], which is not a valid subsequence because it cannot be created by only deleting elements in the original sequence.

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#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("%lld\n",a[1][3]>;

}

return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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;
sets;
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;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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 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("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr  <  t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] a = new int[n];

            String[] aItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            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("(\r\n|[\n\r\u2028\u2029\u0085])?");

            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();
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - 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()
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Direct Connections solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Palindromic Subsets solution in Hackerrank - Hacerrank solution C, C++, java,js, Python