ШТАМПАЊЕ СЕКВЕНЦЕ КОЈА СЕ ПОВЕЋАВА ЗА МАКСИМАЛНУ СУМУ

Пробајте на ГфГ пракси
Проблем подниза са повећањем максималне суме је да се пронађе подниз максималног збира датог низа тако да су сви елементи подниза сортирани у растућем редоследу.
Примери:
    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]   У претходном посту смо расправљали о проблему подниза која се повећава максималном сумом. Међутим, пост је покривао само код који се односи на проналажење максималног збира растуће подниз, али не и на конструкцију подниза. У овом посту ћемо разговарати о томе како конструисати саму подниз који повећава максималну суму.  
  Нека је арр[0..н-1] улазни низ. Дефинишемо вектор Л тако да је Л[и] сам вектор који складишти подниз увећања максималне суме арр[0..и] који се завршава са арр[и]. Стога се за индекс и Л[и] може рекурзивно записати као   
  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 
   
  Горње ДП решење можемо оптимизовати уклањањем функције финдСум(). Уместо тога, можемо да одржавамо други вектор/низ за чување суме максималног сума растуће подниз који се завршава са арр[и].  
     Временска сложеност    од горе наведеног решења за динамичко програмирање је О(н  ² ).    
    Помоћни простор    који програм користи је О(н  ² ).  
     Приступ 2: (    Коришћење          Динамичко програмирање коришћењем О(Н) простора  
  Горњи приступ покрио је како да се конструише подниз са повећањем максималне суме у О(Н  ² ) време и О(Н  ² ) простор. У овом приступу оптимизоваћемо комплексност простора и конструисати подсеквенцу која расте максималном сумом у О(Н  ² )  време и О(Н) простор.  
   Нека је арр[0..н-1] улазни низ.  
  Дефинишемо вектор парова Л тако да Л[и] прво складишти подниз повећања максималног збира од арр[0..и] који се завршава са арр[и] и Л[и].сецонд чува индекс претходног елемента који је коришћен за генерисање збира.  
  Како први елемент нема ниједан претходни елемент, његов индекс би био -1 у Л[0].  
 
  На пример   
  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. Да бисмо конструисали стварну подниз, користићемо индекс ускладиштен у Л[и].сецонд. Кораци за конструисање подсеквенце су приказани у наставку:   
   У векторском резултату складиштите вредност елемента где је пронађена подниз који се повећава за максималну суму (тј. код цуррИндек = 4). Дакле, у вектор резултата ћемо додати арр[цуррИндек].  
  Ажурирајте цуррИндек на Л[цуррИндек].сецонд и понављајте корак 1 док цуррИндек не буде -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 
     Временска сложеност:    О(Н  ² )   
    Сложеност простора:    О(Н)