하위 가중치

Question

**Problem: ----------------- 
========================================== 

시퀀스의 하위 시퀀스는 시퀀스에서 0 개 이상의 요소를 삭제하여 얻은 시퀀스입니다. 모든 원소가 A = [(a1, w1), (a2, w2), ..., (aN, wN)]의 쌍인 시퀀스 A가 주어진다. ,모든 i (1 < = 1 <M)에 대해 bi < bi + 1이면 증가한다고합니다. 무게 (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.** 

Answer 1

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Scanner; 

public class Solution { 
    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     int T = scanner.nextInt(); 
     ArrayList<Input> testInput = new ArrayList<Input>(T); 

     for (int i = 0; i < T; i++) { 
      Input input = new Input(); 
      input.N = scanner.nextInt(); 

      input.value = new int[input.N]; 
      input.weight = new int[input.N]; 

      for (int j = 0; j < input.N; j++) { 
       input.value[j] = scanner.nextInt(); 
      } 

      for (int j = 0; j < input.N; j++) { 
       input.weight[j] = scanner.nextInt(); 
      } 

      testInput.add(input); 
     } 

     int maxSum = 0; 
     for (int i = 0; i < T; i++) { 
      maxSum = findMaxSubsequenceSum(testInput.get(i)); 
      System.out.println(maxSum); 
     } 
    } 

    private static int findMaxSubsequenceSum(Input input) { 
     HashMap<Integer, ArrayList<Integer>> map = input.getInputMap(); 
     ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>(map.values()); 
     int[] index = new int[map.size()]; 
     Arrays.fill(index, 0); 
     int maxSum = getMaxSumInSequence(lists, index); 
     return maxSum; 
    } 

    private static int getMaxSumInSequence(ArrayList<ArrayList<Integer>> lists, int index[]) { 
     int result = 0; 
     int maxSum = 0; 
     boolean indexUpdate = true; 
     int maxListLength = lists.get(0).size(); 

     while (isValidSequence(index) && indexUpdate) { 
      result = addAllListItem(lists, index); 
      if (maxSum < result) { 
       maxSum = result; 
      } 
      indexUpdate = updateIndex(maxListLength, index); 
     } 
     return maxSum; 
    } 

    private static int addAllListItem(List<ArrayList<Integer>> lists, int index[]) { 
     int result = 0; 
     for (int i = 0; i < lists.size(); i++) { 
      result += lists.get(i).get(index[i]); 
     } 
     return result; 
    } 

    private static boolean isValidSequence(int index[]) { 
     int i = index[0]; 
     boolean result = false; 

     for (int l = 1; l < index.length; l++) { 
      if (i <= index[l]) { 
       result = true; 
      } else { 
       result = false; 
      } 
      i = index[l]; 
     } 
     return result; 
    } 

    private static boolean updateIndex(int maxIndex, int index[]) { 
     boolean result = false; 

     if (index[0] == maxIndex - 1) { 
      return result; 
     } 

     int indexSize = index.length - 1; 
     if (index[0] == index[indexSize]) { 
      index[indexSize]++; 
      result = true; 
     } else { 
      for (int i = indexSize; i > 0; i--) { 
       int indexValue = index[i]; 
       if (indexValue > index[i - 1]) { 
        index[i - 1]++; 
        result = true; 
        break; 
       } 
      } 
     } 
     return result; 
    } 

    static class Input { 
     public int N; 
     public int[] value; 
     public int[] weight; 

     public HashMap<Integer, ArrayList<Integer>> getInputMap() { 
      HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); 
      for (int i = 0; i < N; i++) { 
       int key = value[i]; 
       int item = weight[i]; 

       if (map.containsKey(Integer.valueOf(key))) { 
        map.get(Integer.valueOf(key)).add(item); 
       } else { 
        ArrayList<Integer> list = new ArrayList<Integer>(); 
        list.add(new Integer(item)); 
        map.put(new Integer(key), list); 
       } 
      } 
      return map; 
     } 
    } 
}