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 = [(a_{1}, w_{1}), (a_{2}, w_{2}),..., (a_{N}, w_{N})].

For a subseqence B = [(b_{1}, v_{1}), (b_{2}, v_{2}), ...., (b_{M}, v_{M})] of the given sequence : 

We call it increasing if for every i (1 <= i < M ) , b_{i} < b_{i+1}.
Weight(B) = v_{1} + v_{2} + ... + v_{M}.  

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 a_{1}, a_{2} ,... , a_{N} separated by a single space. The next line contains w_{1}, w_{2}, ..., w_{N} 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 <= a_{i} <= $10^{9}$, where i ∈ [1..N] 

1 <= w_{i} <= $10^{9}$, 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.

Difficulty: HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	a = map(int, input().split())
	w = map(int, input().split())
	maw = [(0, 0)]
	nmaw = 1
	for (ai, wi) in zip(a, w):
		j1 = bisect.bisect_left(maw, (ai, 0))
		(aj, wj) = maw[j1 - 1]
		aw = awi = (ai, wi + wj)
		while j1 < len(maw) and maw[j1][1] <= wi + wj:
			del maw[j1]
		if j1 >= len(maw) or maw[j1][0] > ai:
			maw.insert(j1, (ai, wi + wj))
	print(max((wi for (ai, wi) in maw)))


def search_weights(weights, a):
	if len(weights) == 0:
		return (False, 0)
	(low, high) = (0, len(weights) - 1)
	while low < high and weights[low][0] <= a and (a <= weights[high][0]):
		mid = low + (high - low) * (a - weights[low][0]) // (weights[high][0] - weights[low][0])
		if a < weights[mid][0]:
			high = mid - 1
		elif weights[mid][0] < a:
			low = mid + 1
		else:
			return (True, mid)
	if a < weights[low][0]:
		return (False, low)
	if weights[high][0] < a:
		return (False, high + 1)
	return (True, low)
T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	a = [int(x) for x in input().strip().split()]
	w = [int(x) for x in input().strip().split()]
	weights = [(0, 0)]
	for n in range(N):
		(found, index) = search_weights(weights, a[n])
		prev_weight = 0
		if index > 0:
			prev_weight = weights[index - 1][1]
		curr_weight = prev_weight + w[n]
		did_add = False
		if found:
			if weights[index][1] < curr_weight:
				weights[index] = (a[n], curr_weight)
				did_add = True
		elif index == 0 or weights[index - 1][0] < curr_weight:
			weights.insert(index, (a[n], curr_weight))
			did_add = True
		if did_add:
			check_index = index + 1
			while check_index < len(weights) and weights[check_index][1] <= curr_weight:
				weights.pop(check_index)
	print(weights[-1][1])


class Node:

	def __init__(self, v, w):
		self.v = v
		self.w = w
		self.left = self.right = None

def find(r, v, w, m):
	if v == r.v:
		r.w = max(r.w, m + w)
		return r.w
	if v < r.v:
		if r.left:
			t = find(r.left, v, w, m)
			r.w = max(r.w, t)
			return t
		else:
			r.left = Node(v, m + w)
			r.w = max(r.w, r.left.w)
			return r.left.w
	if r.right:
		return find(r.right, v, w, max(m, r.w))
	r.right = Node(v, max(m, r.w) + w)
	return r.right.w
for _ in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	w = list(map(int, input().strip().split()))
	r = Node(a[0], w[0])
	ans = w[0]
	for i in range(1, n):
		ans = max(ans, find(r, a[i], w[i], 0))
	print(ans)


from bisect import bisect_left, bisect_right

def get_max_BIT(T, i):
	total = 0
	i += 1
	i = min(i, len(T) - 1)
	while i > 0:
		total = max(total, T[i])
		i -= i & -i
	return total

def set_BIT(T, i, v):
	i += 1
	while i < len(T):
		T[i] = max(T[i], v)
		i += i & -i

def build_BIT(seq):
	n = len(seq)
	T = [0] * (n + 1)
	for (i, s) in enumerate(seq):
		set_BIT(T, i, s)
	return T
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	A = [int(a) for a in input().strip().split(' ')]
	W = [int(w) for w in input().strip().split(' ')]
	A_sorted = sorted(A)
	T = build_BIT([0] * n)
	result = 0
	for (a, w) in zip(A, W):
		smaller_a_range = bisect_left(A_sorted, a)
		max_weight_sum_so_far = get_max_BIT(T, smaller_a_range - 1) if smaller_a_range > 0 else 0
		new_weight_sum = max_weight_sum_so_far + w
		result = max(result, new_weight_sum)
		set_BIT(T, smaller_a_range, new_weight_sum)
	print(result)


stin = lambda : list(map(int, input().strip().split()))

def update(bit, idx, v):
	while idx < bit[0] and bit[idx] < v:
		bit[idx] = v
		idx += idx & -idx

def get(bit, idx):
	res = 0
	while idx > 0:
		res = max(res, bit[idx])
		idx -= idx & -idx
	return res
for _ in range(int(input())):
	input()
	seq = stin()
	ws = stin()
	key2idx = dict(((k, i) for (i, k) in enumerate(sorted(set(seq)), 1)))
	N = len(key2idx)
	bit = [0] * (N + 1)
	bit[0] = N + 1
	for (a, w) in zip(seq, ws):
		idx = key2idx[a]
		update(bit, idx, get(bit, idx - 1) + w)
	print(get(bit, N))


T = int(input())

class Node:

	def __init__(self, value, weight):
		self.value = value
		self.weight = weight
		self.next = None
		self.prev = None

	def append(self, v, w):
		x = self
		biggestweight = 0
		y = None
		while x is not None and x.value >= v:
			biggestweight = x.weight
			y = x
			x = x.prev
		if x is not None:
			newweight = x.weight + w
			z = Node(v, newweight)
			x.next = z
			z.prev = x
		else:
			newweight = w
		if y is not None and y.value == v:
			if y.weight > newweight:
				return self
		z = Node(v, newweight)
		if x is not None:
			x.next = z
			z.prev = x
		while y is not None and y.weight < newweight:
			y = y.next
		z.next = y
		if y is not None:
			y.prev = z
			return self
		return z
for _ in range(T):
	N = int(input())
	values = [int(num) for num in input().split()]
	weights = [int(num) for num in input().split()]
	tail = Node(values[0], weights[0])
	for i in range(1, N):
		tail = tail.append(values[i], weights[i])
	print(tail.weight)


import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	a = map(int, input().split())
	w = map(int, input().split())
	maw = [(0, 0)]
	nmaw = 1
	for (ai, wi) in zip(a, w):
		j1 = bisect.bisect_left(maw, (ai, 0))
		(aj, wj) = maw[j1 - 1]
		aw = awi = (ai, wi + wj)
		while j1 < len(maw) and maw[j1][1] <= wi + wj:
			del maw[j1]
		if j1 >= len(maw) or maw[j1][0] > ai:
			maw.insert(j1, (ai, wi + wj))
	print(max((wi for (ai, wi) in maw)))


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)


import math
import os
import random
import re
import sys
import sys
import bisect
for t in range(int(sys.stdin.readline().strip())):
	sys.stdin.readline()
	a_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	w_list = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	max_a = []
	max_a_to_w = {}

	def get_total(a):
		if not max_a:
			return 0
		else:
			i = bisect.bisect(max_a, a)
			if i == 0 and a < max_a[i]:
				return 0
			elif i + 1 > len(max_a):
				return max_a_to_w[max_a[-1]]
			else:
				return max_a_to_w[max_a[i - 1]]

	def add_a_w(a, w):
		i = bisect.bisect_left(max_a, a)
		s = max_a[i:]
		n = 0
		for an in s:
			wn = max_a_to_w[an]
			if wn <= w:
				n += 1
			else:
				break
		del max_a[i:i + n]
		max_a.insert(i, a)
		max_a_to_w[a] = w
	for i in range(len(a_list)):
		a = a_list[i]
		w = w_list[i]
		cur_weight = get_total(a)
		prior_weight = get_total(a - 1)
		take_weight = prior_weight + w
		if take_weight > cur_weight:
			add_a_w(a, take_weight)
	result = get_total(float('inf'))
	print(result)