최대 합계 증가 하위 시퀀스 인쇄

GfG Practice에서 사용해 보세요.
최대 합 증가 부분 수열 문제는 주어진 수열의 모든 요소가 오름차순으로 정렬되도록 해당 수열의 최대 합 부분 수열을 찾는 것입니다.
예:
    Input:      [1 101 2 3 100 4 5]   
    Output:     [1 2 3 100]   
  
    Input:      [3 4 5 10]   
    Output:     [3 4 5 10]   
  
    Input:      [10 5 4 3]   
    Output:     [10]   
  
    Input:      [3 2 6 4 5 1]   
    Output:     [3 4 5]   이전 게시물에서 우리는 최대 합 증가 부분 수열 문제에 대해 논의했습니다. 그러나 게시물에서는 증가하는 하위 시퀀스의 최대 합계를 찾는 것과 관련된 코드만 다루었지만 하위 시퀀스 구성에는 적용되지 않았습니다. 이번 포스팅에서는 최대 합 증가 부분 수열 자체를 구성하는 방법에 대해 논의하겠습니다.  
  arr[0..n-1]을 입력 배열로 둡니다. 우리는 L[i] 자체가 arr[i]로 끝나는 arr[0..i]의 최대 합계 증가 부분 시퀀스를 저장하는 벡터가 되도록 벡터 L을 정의합니다. 따라서 인덱스 i에 대해 L[i]는 다음과 같이 재귀적으로 작성될 수 있습니다.   
  L[0] = {arr[0]}   
 L[i] = {MaxSum(L[j])} + arr[i] where j  < i and arr[j]  < arr[i]   
  = arr[i] if there is no j such that arr[j]  < arr[i]    
 예를 들어 배열 [3 2 6 4 5 1]   
  L[0]: 3   
 L[1]: 2   
 L[2]: 3 6   
 L[3]: 3 4   
 L[4]: 3 4 5   
 L[5]: 1    
 아래는 위의 아이디어를 구현한 것입니다.   
 C++      /* Dynamic Programming solution to construct    Maximum Sum Increasing Subsequence */   #include          #include         using     namespace     std  ;   // Utility function to calculate sum of all   // vector elements   int     findSum  (  vector   <  int  >     arr  )   {      int     sum     =     0  ;      for     (  int     i     :     arr  )      sum     +=     i  ;      return     sum  ;   }   // Function to construct Maximum Sum Increasing   // Subsequence   void     printMaxSumIS  (  int     arr  []     int     n  )   {      // L[i] - The Maximum Sum Increasing      // Subsequence that ends with arr[i]      vector   <  vector   <  int  >     >     L  (  n  );      // L[0] is equal to arr[0]      L  [  0  ].  push_back  (  arr  [  0  ]);      // start from index 1      for     (  int     i     =     1  ;     i      <     n  ;     i  ++  )     {      // for every j less than i      for     (  int     j     =     0  ;     j      <     i  ;     j  ++  )     {      /* L[i] = {MaxSum(L[j])} + arr[i]    where j  < i and arr[j]  < arr[i] */      if     ((  arr  [  i  ]     >     arr  [  j  ])      &&     (  findSum  (  L  [  i  ])      <     findSum  (  L  [  j  ])))      L  [  i  ]     =     L  [  j  ];      }      // L[i] ends with arr[i]      L  [  i  ].  push_back  (  arr  [  i  ]);      // L[i] now stores Maximum Sum Increasing      // Subsequence of arr[0..i] that ends with      // arr[i]      }      vector   <  int  >     res     =     L  [  0  ];      // find max      for     (  vector   <  int  >     x     :     L  )      if     (  findSum  (  x  )     >     findSum  (  res  ))      res     =     x  ;      // max will contain result      for     (  int     i     :     res  )      cout      < <     i      < <     ' '  ;      cout      < <     endl  ;   }   // Driver Code   int     main  ()   {      int     arr  []     =     {     3       2       6       4       5       1     };      int     n     =     sizeof  (  arr  )     /     sizeof  (  arr  [  0  ]);      // construct and print Max Sum IS of arr      printMaxSumIS  (  arr       n  );      return     0  ;   }   
  Java      /* Dynamic Programming solution to construct   Maximum Sum Increasing Subsequence */   import     java.util.*  ;   class   GFG     {      // Utility function to calculate sum of all      // vector elements      static     int     findSum  (  Vector   <  Integer  >     arr  )      {      int     sum     =     0  ;      for     (  int     i     :     arr  )      sum     +=     i  ;      return     sum  ;      }      // Function to construct Maximum Sum Increasing      // Subsequence      static     void     printMaxSumIs  (  int  []     arr       int     n  )      {      // L[i] - The Maximum Sum Increasing      // Subsequence that ends with arr[i]      @SuppressWarnings  (  'unchecked'  )      Vector   <  Integer  >[]     L     =     new     Vector  [  n  ]  ;      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      L  [  i  ]     =     new     Vector   <>  ();      // L[0] is equal to arr[0]      L  [  0  ]  .  add  (  arr  [  0  ]  );      // start from index 1      for     (  int     i     =     1  ;     i      <     n  ;     i  ++  )     {      // for every j less than i      for     (  int     j     =     0  ;     j      <     i  ;     j  ++  )     {      /*    * L[i] = {MaxSum(L[j])} + arr[i]    where j  < i and arr[j]  < arr[i]    */      if     ((  arr  [  i  ]     >     arr  [  j  ]  )      &&     (  findSum  (  L  [  i  ]  )      <     findSum  (  L  [  j  ]  )))     {      for     (  int     k     :     L  [  j  ]  )      if     (  !  L  [  i  ]  .  contains  (  k  ))      L  [  i  ]  .  add  (  k  );      }      }      // L[i] ends with arr[i]      L  [  i  ]  .  add  (  arr  [  i  ]  );      // L[i] now stores Maximum Sum Increasing      // Subsequence of arr[0..i] that ends with      // arr[i]      }      Vector   <  Integer  >     res     =     new     Vector   <>  (  L  [  0  ]  );      // res = L[0];      // find max      for     (  Vector   <  Integer  >     x     :     L  )      if     (  findSum  (  x  )     >     findSum  (  res  ))      res     =     x  ;      // max will contain result      for     (  int     i     :     res  )      System  .  out  .  print  (  i     +     ' '  );      System  .  out  .  println  ();      }      // Driver Code      public     static     void     main  (  String  []     args  )      {      int  []     arr     =     {     3       2       6       4       5       1     };      int     n     =     arr  .  length  ;      // construct and print Max Sum IS of arr      printMaxSumIs  (  arr       n  );      }   }   // This code is contributed by   // sanjeev2552   
  Python      # Dynamic Programming solution to construct   # Maximum Sum Increasing Subsequence */   # Utility function to calculate sum of all   # vector elements   def   findSum  (  arr  ):   summ   =   0   for   i   in   arr  :   summ   +=   i   return   summ   # Function to construct Maximum Sum Increasing   # Subsequence   def   printMaxSumIS  (  arr     n  ):   # L[i] - The Maximum Sum Increasing   # Subsequence that ends with arr[i]   L   =   [[]   for   i   in   range  (  n  )]   # L[0] is equal to arr[0]   L  [  0  ]  .  append  (  arr  [  0  ])   # start from index 1   for   i   in   range  (  1     n  ):   # for every j less than i   for   j   in   range  (  i  ):   # L[i] = {MaxSum(L[j])} + arr[i]   # where j  < i and arr[j]  < arr[i]   if   ((  arr  [  i  ]   >   arr  [  j  ])   and   (  findSum  (  L  [  i  ])    <   findSum  (  L  [  j  ]))):   for   e   in   L  [  j  ]:   if   e   not   in   L  [  i  ]:   L  [  i  ]  .  append  (  e  )   # L[i] ends with arr[i]   L  [  i  ]  .  append  (  arr  [  i  ])   # L[i] now stores Maximum Sum Increasing   # Subsequence of arr[0..i] that ends with   # arr[i]   res   =   L  [  0  ]   # find max   for   x   in   L  :   if   (  findSum  (  x  )   >   findSum  (  res  )):   res   =   x   # max will contain result   for   i   in   res  :   print  (  i     end  =  ' '  )   # Driver Code   arr   =   [  3     2     6     4     5     1  ]   n   =   len  (  arr  )   # construct and prMax Sum IS of arr   printMaxSumIS  (  arr     n  )   # This code is contributed by Mohit Kumar   
  C#      /* Dynamic Programming solution to construct   Maximum Sum Increasing Subsequence */   using     System  ;   using     System.Collections.Generic  ;   class     GFG     {      // Utility function to calculate sum of all      // vector elements      static     int     findSum  (  List   <  int  >     arr  )      {      int     sum     =     0  ;      foreach  (  int     i     in     arr  )     sum     +=     i  ;      return     sum  ;      }      // Function to construct Maximum Sum Increasing      // Subsequence      static     void     printMaxSumIs  (  int  []     arr       int     n  )      {      // L[i] - The Maximum Sum Increasing      // Subsequence that ends with arr[i]      List   <  int  >  []     L     =     new     List   <  int  >  [     n     ];      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      L  [  i  ]     =     new     List   <  int  >  ();      // L[0] is equal to arr[0]      L  [  0  ].  Add  (  arr  [  0  ]);      // start from index 1      for     (  int     i     =     1  ;     i      <     n  ;     i  ++  )     {      // for every j less than i      for     (  int     j     =     0  ;     j      <     i  ;     j  ++  )     {      /*    * L[i] = {MaxSum(L[j])} + arr[i]    where j  < i and arr[j]  < arr[i]    */      if     ((  arr  [  i  ]     >     arr  [  j  ])      &&     (  findSum  (  L  [  i  ])      <     findSum  (  L  [  j  ])))     {      foreach  (  int     k     in      L  [  j  ])     if     (  !  L  [  i  ].  Contains  (  k  ))      L  [  i  ]      .  Add  (  k  );      }      }      // L[i] ends with arr[i]      L  [  i  ].  Add  (  arr  [  i  ]);      // L[i] now stores Maximum Sum Increasing      // Subsequence of arr[0..i] that ends with      // arr[i]      }      List   <  int  >     res     =     new     List   <  int  >  (  L  [  0  ]);      // res = L[0];      // find max      foreach  (  List   <  int  >     x     in     L  )     if     (  findSum  (  x  )      >     findSum  (  res  ))     res      =     x  ;      // max will contain result      foreach  (  int     i     in     res  )     Console  .  Write  (  i     +     ' '  );      Console  .  WriteLine  ();      }      // Driver Code      public     static     void     Main  (  String  []     args  )      {      int  []     arr     =     {     3       2       6       4       5       1     };      int     n     =     arr  .  Length  ;      // construct and print Max Sum IS of arr      printMaxSumIs  (  arr       n  );      }   }   // This code is contributed by PrinciRaj1992   
  JavaScript       <  script  >   /* Dynamic Programming solution to construct   Maximum Sum Increasing Subsequence */          // Utility function to calculate sum of all      // vector elements      function     findSum  (  arr  )      {      let     sum     =     0  ;      for     (  let     i  =  0  ;  i   <  arr  .  length  ;  i  ++  )      sum     +=     arr  [  i  ];      return     sum  ;      }          // Function to construct Maximum Sum Increasing      // Subsequence      function     printMaxSumIs  (  arr    n  )      {      // L[i] - The Maximum Sum Increasing      // Subsequence that ends with arr[i]          let     L     =     new     Array  (  n  );          for     (  let     i     =     0  ;     i      <     n  ;     i  ++  )      L  [  i  ]     =     [];          // L[0] is equal to arr[0]      L  [  0  ].  push  (  arr  [  0  ]);          // start from index 1      for     (  let     i     =     1  ;     i      <     n  ;     i  ++  )     {          // for every j less than i      for     (  let     j     =     0  ;     j      <     i  ;     j  ++  )     {          /*    * L[i] = {MaxSum(L[j])} + arr[i]    where j  < i and arr[j]  < arr[i]    */      if     ((  arr  [  i  ]     >     arr  [  j  ])      &&     (  findSum  (  L  [  i  ])      <     findSum  (  L  [  j  ])))         {      for     (  let     k  =  0  ;  k   <  L  [  j  ].  length  ;  k  ++  )      if     (  !  L  [  i  ].  includes  (  L  [  j  ][  k  ]))      L  [  i  ].  push  (  L  [  j  ][  k  ]);      }      }          // L[i] ends with arr[i]      L  [  i  ].  push  (  arr  [  i  ]);          // L[i] now stores Maximum Sum Increasing      // Subsequence of arr[0..i] that ends with      // arr[i]      }          let     res     =     L  [  0  ];      // res = L[0];          // find max      for     (  let     x  =  0  ;  x   <  L  .  length  ;  x  ++  )      if     (  findSum  (  L  [  x  ])     >     findSum  (  res  ))      res     =     L  [  x  ];          // max will contain result      for     (  let     i  =  0  ;  i   <  res  .  length  ;  i  ++  )      document  .  write  (  res  [  i  ]     +     ' '  );      document  .  write  (  '  
'  );      }          // Driver Code      let     arr  =  [  3       2       6       4       5       1  ];      let     n     =     arr  .  length  ;          // construct and print Max Sum IS of arr      printMaxSumIs  (  arr       n  );       // This code is contributed by unknown2108    <  /script>   
    
  산출   3 4 5 
   
  findSum() 함수를 제거하여 위의 DP 솔루션을 최적화할 수 있습니다. 대신 arr[i]로 끝나는 최대 합 증가 하위 시퀀스의 합을 저장하기 위해 또 다른 벡터/배열을 유지할 수 있습니다.  
     시간 복잡도    위의 동적 프로그래밍 솔루션은 O(n  ² ).    
    보조 공간    프로그램에서 사용하는 O(n  ² ).  
     접근법 2: (    사용          O(N) 공간을 이용한 동적 프로그래밍  
  위의 접근 방식은 O(N에서 최대 합계 증가 부분 시퀀스를 구성하는 방법을 다루었습니다.  ² ) 시간과 O(N  ² ) 공간. 이 접근 방식에서는 공간 복잡도를 최적화하고 O(N)으로 최대 합계 증가 부분 시퀀스를 구성합니다.  ² )  시간 및 O(N) 공간.  
   arr[0..n-1]을 입력 배열로 둡니다.  
  L[i]가 먼저 arr[i]로 끝나는 arr[0..i]의 최대 합계 증가 부분 시퀀스를 저장하고 L[i].second가 합계를 생성하는 데 사용된 이전 요소의 인덱스를 저장하도록 쌍 L의 벡터를 정의합니다.  
  첫 번째 요소에는 이전 요소가 없으므로 해당 인덱스는 L[0]에서 -1이 됩니다.  
 
  예를 들어   
  array = [3 2 6 4 5 1]   
  
 L[0]: {3 -1}   
 L[1]: {2 1}   
 L[2]: {9 0}   
 L[3]: {7 0}   
 L[4]: {12 3}   
 L[5]: {1 5}   위에서 볼 수 있듯이 최대 합계 증가 하위 시퀀스의 값은 12입니다. 실제 하위 시퀀스를 구성하기 위해 L[i].second에 저장된 인덱스를 사용합니다. 하위 시퀀스를 구성하는 단계는 다음과 같습니다.   
   벡터 결과에서 최대 합계 증가 하위 시퀀스가 발견된 요소의 값을 저장합니다(예: currIndex = 4). 따라서 결과 벡터에 arr[currIndex]를 추가합니다.  
  currIndex를 L[currIndex].second로 업데이트하고 currIndex가 -1이 아니거나 변경되지 않을 때까지(예: currIndex == PreviousIndex) 1단계를 반복합니다.  
  결과 벡터의 요소를 역순으로 표시합니다.  
 
  다음은 위의 아이디어를 구현한 것입니다.   
 C++14      /* Dynamic Programming solution to construct   Maximum Sum Increasing Subsequence */   #include          using     namespace     std  ;   // Function to construct and print the Maximum Sum   // Increasing Subsequence   void     constructMaxSumIS  (  vector   <  int  >     arr       int     n  )   {      // L[i] stores the value of Maximum Sum Increasing      // Subsequence that ends with arr[i] and the index of      // previous element used to construct the Subsequence      vector   <  pair   <  int       int  >     >     L  (  n  );      int     index     =     0  ;      for     (  int     i     :     arr  )     {      L  [  index  ]     =     {     i       index     };      index  ++  ;      }      // Set L[0].second equal to -1      L  [  0  ].  second     =     -1  ;      // start from index 1      for     (  int     i     =     1  ;     i      <     n  ;     i  ++  )     {      // for every j less than i      for     (  int     j     =     0  ;     j      <     i  ;     j  ++  )     {      if     (  arr  [  i  ]     >     arr  [  j  ]      and     L  [  i  ].  first      <     arr  [  i  ]     +     L  [  j  ].  first  )     {      L  [  i  ].  first     =     arr  [  i  ]     +     L  [  j  ].  first  ;      L  [  i  ].  second     =     j  ;      }      }      }      int     maxi     =     INT_MIN       currIndex       track     =     0  ;      for     (  auto     p     :     L  )     {      if     (  p  .  first     >     maxi  )     {      maxi     =     p  .  first  ;      currIndex     =     track  ;      }      track  ++  ;      }      // Stores the final Subsequence      vector   <  int  >     result  ;      // Index of previous element      // used to construct the Subsequence      int     prevoiusIndex  ;      while     (  currIndex     >=     0  )     {      result  .  push_back  (  arr  [  currIndex  ]);      prevoiusIndex     =     L  [  currIndex  ].  second  ;      if     (  currIndex     ==     prevoiusIndex  )      break  ;      currIndex     =     prevoiusIndex  ;      }      for     (  int     i     =     result  .  size  ()     -     1  ;     i     >=     0  ;     i  --  )      cout      < <     result  [  i  ]      < <     ' '  ;   }   // Driver Code   int     main  ()   {      vector   <  int  >     arr     =     {     1       101       2       3       100       4       5     };      int     n     =     arr  .  size  ();      // Function call      constructMaxSumIS  (  arr       n  );      return     0  ;   }   
  Java      // Dynamic Programming solution to construct   // Maximum Sum Increasing Subsequence    import     java.util.*  ;   import     java.awt.Point  ;   class   GFG  {       // Function to construct and print the Maximum Sum   // Increasing Subsequence   static     void     constructMaxSumIS  (  List   <  Integer  >     arr       int     n  )   {          // L.get(i) stores the value of Maximum Sum Increasing      // Subsequence that ends with arr.get(i) and the index of      // previous element used to construct the Subsequence      List   <  Point  >     L     =     new     ArrayList   <  Point  >  ();      int     index     =     0  ;      for  (  int     i     :     arr  )      {      L  .  add  (  new     Point  (  i       index  ));      index  ++  ;      }      // Set L[0].second equal to -1      L  .  set  (  0       new     Point  (  L  .  get  (  0  ).  x       -  1  ));      // Start from index 1      for  (  int     i     =     1  ;     i      <     n  ;     i  ++  )      {          // For every j less than i      for  (  int     j     =     0  ;     j      <     i  ;     j  ++  )      {      if     (  arr  .  get  (  i  )     >     arr  .  get  (  j  )     &&      L  .  get  (  i  ).  x      <     arr  .  get  (  i  )     +      L  .  get  (  j  ).  x  )         {      L  .  set  (  i       new     Point  (  arr  .  get  (  i  )     +      L  .  get  (  j  ).  x       j  ));      }      }      }      int     maxi     =     -  100000000       currIndex     =     0       track     =     0  ;      for  (  Point     p     :     L  )         {      if     (  p  .  x     >     maxi  )      {      maxi     =     p  .  x  ;      currIndex     =     track  ;      }      track  ++  ;      }      // Stores the final Subsequence      List   <  Integer  >     result     =     new     ArrayList   <  Integer  >  ();      // Index of previous element      // used to construct the Subsequence      int     prevoiusIndex  ;      while     (  currIndex     >=     0  )         {      result  .  add  (  arr  .  get  (  currIndex  ));      prevoiusIndex     =     L  .  get  (  currIndex  ).  y  ;      if     (  currIndex     ==     prevoiusIndex  )      break  ;      currIndex     =     prevoiusIndex  ;      }      for  (  int     i     =     result  .  size  ()     -     1  ;     i     >=     0  ;     i  --  )      System  .  out  .  print  (  result  .  get  (  i  )     +     ' '  );   }      // Driver Code   public     static     void     main  (  String     []  s  )   {      List   <  Integer  >     arr     =     new     ArrayList   <  Integer  >  ();      arr  .  add  (  1  );      arr  .  add  (  101  );      arr  .  add  (  2  );      arr  .  add  (  3  );      arr  .  add  (  100  );      arr  .  add  (  4  );      arr  .  add  (  5  );          int     n     =     arr  .  size  ();      // Function call      constructMaxSumIS  (  arr       n  );      }   }   // This code is contributed by rutvik_56    
  Python      # Dynamic Programming solution to construct   # Maximum Sum Increasing Subsequence    import   sys   # Function to construct and print the Maximum Sum   # Increasing Subsequence   def   constructMaxSumIS  (  arr     n  )   :   # L[i] stores the value of Maximum Sum Increasing   # Subsequence that ends with arr[i] and the index of   # previous element used to construct the Subsequence   L   =   []   index   =   0   for   i   in   arr   :   L  .  append  ([  i     index  ])   index   +=   1   # Set L[0].second equal to -1   L  [  0  ][  1  ]   =   -  1   # start from index 1   for   i   in   range  (  1     n  )   :   # for every j less than i   for   j   in   range  (  i  )   :   if   (  arr  [  i  ]   >   arr  [  j  ]   and   L  [  i  ][  0  ]    <   arr  [  i  ]   +   L  [  j  ][  0  ])   :   L  [  i  ][  0  ]   =   arr  [  i  ]   +   L  [  j  ][  0  ]   L  [  i  ][  1  ]   =   j   maxi     currIndex     track   =   -  sys  .  maxsize     0     0   for   p   in   L   :   if   (  p  [  0  ]   >   maxi  )   :   maxi   =   p  [  0  ]   currIndex   =   track   track   +=   1   # Stores the final Subsequence   result   =   []   while   (  currIndex   >=   0  )   :   result  .  append  (  arr  [  currIndex  ])   prevoiusIndex   =   L  [  currIndex  ][  1  ]   if   (  currIndex   ==   prevoiusIndex  )   :   break   currIndex   =   prevoiusIndex   for   i   in   range  (  len  (  result  )   -   1     -  1     -  1  )   :   print  (  result  [  i  ]      end   =   ' '  )   arr   =   [   1     101     2     3     100     4     5   ]   n   =   len  (  arr  )   # Function call   constructMaxSumIS  (  arr     n  )   # This code is contributed by divyeshrabadiya07   
  C#      /* Dynamic Programming solution to construct   Maximum Sum Increasing Subsequence */   using     System  ;   using     System.Collections.Generic  ;      class     GFG      {          // Function to construct and print the Maximum Sum      // Increasing Subsequence      static     void     constructMaxSumIS  (  List   <  int  >     arr       int     n  )      {          // L[i] stores the value of Maximum Sum Increasing      // Subsequence that ends with arr[i] and the index of      // previous element used to construct the Subsequence      List   <  Tuple   <  int       int  >>     L     =     new     List   <  Tuple   <  int       int  >>  ();          int     index     =     0  ;      foreach  (  int     i     in     arr  )     {      L  .  Add  (  new     Tuple   <  int       int  >  (  i       index  ));      index  ++  ;      }          // Set L[0].second equal to -1      L  [  0  ]     =     new     Tuple   <  int       int  >  (  L  [  0  ].  Item1       -  1  );          // start from index 1      for     (  int     i     =     1  ;     i      <     n  ;     i  ++  )      {          // for every j less than i      for     (  int     j     =     0  ;     j      <     i  ;     j  ++  )      {      if     (  arr  [  i  ]     >     arr  [  j  ]     &&      L  [  i  ].  Item1      <     arr  [  i  ]     +      L  [  j  ].  Item1  )         {      L  [  i  ]     =     new     Tuple   <  int           int  >  (  arr  [  i  ]     +     L  [  j  ].  Item1       j  );      }      }      }          int     maxi     =     Int32  .  MinValue           currIndex     =     0       track     =     0  ;          foreach  (  Tuple   <  int       int  >     p     in     L  )         {      if     (  p  .  Item1     >     maxi  )      {      maxi     =     p  .  Item1  ;      currIndex     =     track  ;      }      track  ++  ;      }          // Stores the final Subsequence      List   <  int  >     result     =     new     List   <  int  >  ();          // Index of previous element      // used to construct the Subsequence      int     prevoiusIndex  ;          while     (  currIndex     >=     0  )         {      result  .  Add  (  arr  [  currIndex  ]);      prevoiusIndex     =     L  [  currIndex  ].  Item2  ;          if     (  currIndex     ==     prevoiusIndex  )      break  ;          currIndex     =     prevoiusIndex  ;      }          for     (  int     i     =     result  .  Count     -     1  ;     i     >=     0  ;     i  --  )      Console  .  Write  (  result  [  i  ]     +     ' '  );      }         static     void     Main  ()      {      List   <  int  >     arr     =     new     List   <  int  >  (  new         int  []     {     1       101       2       3       100       4       5     });      int     n     =     arr  .  Count  ;          // Function call      constructMaxSumIS  (  arr       n  );         }   }   // This code is contributed by divyesh072019   
  JavaScript       <  script  >   // Dynamic Programming solution to construct   // Maximum Sum Increasing Subsequence    // Function to construct and print the Maximum Sum   // Increasing Subsequence   function     constructMaxSumIS  (  arr       n  ){      // L[i] stores the value of Maximum Sum Increasing      // Subsequence that ends with arr[i] and the index of      // previous element used to construct the Subsequence      let     L     =     []      let     index     =     0      for  (  let     i     of     arr  ){      L  .  push  ([  i       index  ])      index     +=     1      }      // Set L[0].second equal to -1      L  [  0  ][  1  ]     =     -  1      // start from index 1      for  (  let     i  =  1  ;  i   <  n  ;  i  ++  ){          // for every j less than i      for  (  let     j  =  0  ;  j   <  i  ;  j  ++  ){      if     (  arr  [  i  ]     >     arr  [  j  ]     &&     L  [  i  ][  0  ]      <     arr  [  i  ]     +     L  [  j  ][  0  ]){      L  [  i  ][  0  ]     =     arr  [  i  ]     +     L  [  j  ][  0  ]      L  [  i  ][  1  ]     =     j      }      }      }      let     maxi     =     Number  .  MIN_VALUE       currIndex     =     0       track     =     0      for  (  let     p     of     L  ){      if     (  p  [  0  ]     >     maxi  ){      maxi     =     p  [  0  ]      currIndex     =     track      }          track     +=     1      }      // Stores the final Subsequence      let     result     =     []      while     (  currIndex     >=     0  ){      result  .  push  (  arr  [  currIndex  ])      let     prevoiusIndex     =     L  [  currIndex  ][  1  ]      if     (  currIndex     ==     prevoiusIndex  )      break      currIndex     =     prevoiusIndex      }      for  (  let     i  =  result  .  length     -     1  ;  i  >=  0  ;  i  --  )         document  .  write  (  result  [  i  ]       ' '  )   }   let     arr     =     [     1       101       2       3       100       4       5     ]   let     n     =     arr  .  length   // Function call   constructMaxSumIS  (  arr       n  )   // This code is contributed by shinjanpatra    <  /script>   
    
  산출   1 2 3 100 
     시간 복잡도:    에  ² )   
    공간 복잡도:    에)