طباعة الحد الأقصى للمبلغ اللاحق المتزايد

جربه على ممارسة GfG
تتمثل مشكلة الحد الأقصى لمجموع التسلسل الفرعي في العثور على الحد الأقصى لمجموع التسلسل الفرعي لتسلسل معين بحيث يتم فرز جميع عناصر التسلسل الفرعي بترتيب متزايد.
أمثلة:
    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 بحيث يكون L[i] في حد ذاته متجهًا يخزن الحد الأقصى للمجموع المتزايد للتسلسل arr[0..i] الذي ينتهي بـ arr[i]. لذلك يمكن كتابة الفهرس 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 
   
  يمكننا تحسين حل DP أعلاه عن طريق إزالة وظيفة findSum(). بدلًا من ذلك، يمكننا الاحتفاظ بمتجه/مصفوفة أخرى لتخزين مجموع الحد الأقصى للتسلسل المتزايد الذي ينتهي بـ arr[i].  
     تعقيد الوقت    من حل البرمجة الديناميكية أعلاه هو O(n  ² ).    
    مساحة مساعدة    المستخدم في البرنامج هو O(n  ² ).  
     النهج 2: (    استخدام          البرمجة الديناميكية باستخدام مساحة O(N).  
  غطى النهج المذكور أعلاه كيفية إنشاء الحد الأقصى للمجموع المتزايد في O(N  ² ) الوقت و O(N  ² ) فضاء. في هذا النهج، سنقوم بتحسين تعقيد الفضاء وبناء الحد الأقصى للمجموع المتزايد في O(N  ² )  الوقت ومساحة O(N).  
   دع arr[0..n-1] يكون مصفوفة الإدخال.  
  نحدد متجهًا للأزواج L بحيث يقوم L[i] أولاً بتخزين الحد الأقصى للتسلسل المتزايد لـ arr[0..i] الذي ينتهي بـ arr[i] وL[i].sec يخزن فهرس العنصر السابق المستخدم لإنشاء المجموع.  
  بما أن العنصر الأول لا يحتوي على أي عنصر سابق، فإن فهرسه سيكون -1 في L[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. لإنشاء التسلسل اللاحق الفعلي، سنستخدم الفهرس المخزن في L[i].ثانية. خطوات بناء اللاحقة موضحة أدناه:   
   في نتيجة المتجهات، قم بتخزين قيمة العنصر حيث تم العثور على الحد الأقصى للمجموع المتزايد (أي في currIndex = 4). لذا سنضيف arr[currIndex] إلى متجه النتيجة.  
  قم بتحديث currIndex إلى L[currIndex].ثانية وكرر الخطوة 1 حتى لا يصبح currIndex -1 أو لا يتغير (أي currIndex == PreviousIndex).  
  عرض عناصر متجه النتيجة بترتيب عكسي.  
 
  وفيما يلي تنفيذ الفكرة المذكورة أعلاه:   
 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 
     تعقيد الوقت:    على  ² )   
    تعقيد الفضاء:    على)