Revisions to How to determine the longest increasing subsequence using dynamic programming?

improved readability; completed imports; added syntax highlighting.

Source Link

edited Nov 29, 2024 at 17:53

2.3k
2
19
26

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();
    
    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

#include <iostream>
#include <vector>
#include <limits>

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s) {
    int best_end = 0;
    int sz = s.size();
    
    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz, -1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for (int i = 1; i < sz; ++i) {
        for (int j = 0; j < i; ++j) {
            if (s[j] < s[i] && memo[i] < memo[j] + 1) {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if (memo[i] > max_length) {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1) {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty()) {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
  auto sz = v.size();
  if(!sz)
    return v;
  std::vector<int> memo(sz, 0);
  std::vector<int> prev(sz, -1);
  memo[0] = 1;
  int best_end = 0;
  int max_length = std::numeric_limits<int>::min();
  for (auto i = 1; i < sz; ++i) {
    for ( auto j = 0; j < i ; ++j) {
      if (s[j] < s[i] && memo[i] < memo[j] + 1) {
        memo[i] = memo[j] + 1;
        prev[i] = j;
      }
    }
    if(memo[i] > max_length) {
      best_end = i;
      max_length = memo[i];
    }
  }

  // create results
  std::vector<int> results;
  results.reserve(v.size());
  auto current = best_end;
  while (current != -1) {
    results.push_back(s[current]);
    current = prev[current];
  }
  std::reverse(results.begin(), results.end());
  return results;
}

#include <iostream>
#include <vector>
#include <limits>

std::vector<int> LIS(const std::vector<int> &v) {
    auto sz = v.size();
    if(!sz)
        return v;
    std::vector<int> memo(sz, 0);
    std::vector<int> prev(sz, -1);
    memo[0] = 1;
    int best_end = 0;
    int max_length = std::numeric_limits<int>::min();
    for (int i = 1; i < sz; ++i) {
        for (int j = 0; j < i ; ++j) {
            if (s[j] < s[i] && memo[i] < memo[j] + 1) {
                memo[i] = memo[j] + 1;
                prev[i] = j;
            }
        }
        if(memo[i] > max_length) {
            best_end = i;
            max_length = memo[i];
        }
    }

    // create results
    std::vector<int> results;
    results.reserve(v.size());
    auto current = best_end;
    while (current != -1) {
        results.push_back(s[current]);
        current = prev[current];
    }
    std::reverse(results.begin(), results.end());
    return results;
}

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();
    
    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
  auto sz = v.size();
  if(!sz)
    return v;
  std::vector<int> memo(sz, 0);
  std::vector<int> prev(sz, -1);
  memo[0] = 1;
  int best_end = 0;
  int max_length = std::numeric_limits<int>::min();
  for (auto i = 1; i < sz; ++i) {
    for ( auto j = 0; j < i ; ++j) {
      if (s[j] < s[i] && memo[i] < memo[j] + 1) {
        memo[i] = memo[j] + 1;
        prev[i] = j;
      }
    }
    if(memo[i] > max_length) {
      best_end = i;
      max_length = memo[i];
    }
  }

  // create results
  std::vector<int> results;
  results.reserve(v.size());
  auto current = best_end;
  while (current != -1) {
    results.push_back(s[current]);
    current = prev[current];
  }
  std::reverse(results.begin(), results.end());
  return results;
}

#include <iostream>
#include <vector>
#include <limits>

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s) {
    int best_end = 0;
    int sz = s.size();
    
    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz, -1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for (int i = 1; i < sz; ++i) {
        for (int j = 0; j < i; ++j) {
            if (s[j] < s[i] && memo[i] < memo[j] + 1) {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if (memo[i] > max_length) {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1) {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty()) {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

#include <iostream>
#include <vector>
#include <limits>

std::vector<int> LIS(const std::vector<int> &v) {
    auto sz = v.size();
    if(!sz)
        return v;
    std::vector<int> memo(sz, 0);
    std::vector<int> prev(sz, -1);
    memo[0] = 1;
    int best_end = 0;
    int max_length = std::numeric_limits<int>::min();
    for (int i = 1; i < sz; ++i) {
        for (int j = 0; j < i ; ++j) {
            if (s[j] < s[i] && memo[i] < memo[j] + 1) {
                memo[i] = memo[j] + 1;
                prev[i] = j;
            }
        }
        if(memo[i] > max_length) {
            best_end = i;
            max_length = memo[i];
        }
    }

    // create results
    std::vector<int> results;
    results.reserve(v.size());
    auto current = best_end;
    while (current != -1) {
        results.push_back(s[current]);
        current = prev[current];
    }
    std::reverse(results.begin(), results.end());
    return results;
}

added 1092 characters in body

Source Link

edited Nov 4, 2015 at 3:09

bjackfly

3.3k
2
30
42

Implementation with no stack just reverse the vector

#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
  auto sz = v.size();
  if(!sz)
    return v;
  std::vector<int> memo(sz, 0);
  std::vector<int> prev(sz, -1);
  memo[0] = 1;
  int best_end = 0;
  int max_length = std::numeric_limits<int>::min();
  for (auto i = 1; i < sz; ++i) {
    for ( auto j = 0; j < i ; ++j) {
      if (s[j] < s[i] && memo[i] < memo[j] + 1) {
        memo[i] = memo[j] + 1;
        prev[i] = j;
      }
    }
    if(memo[i] > max_length) {
      best_end = i;
      max_length = memo[i];
    }
  }

  // create results
  std::vector<int> results;
  results.reserve(v.size());
  auto current = best_end;
  while (current != -1) {
    results.push_back(s[current]);
    current = prev[current];
  }
  std::reverse(results.begin(), results.end());
  return results;
}

Implementation with no stack just reverse the vector

#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
  auto sz = v.size();
  if(!sz)
    return v;
  std::vector<int> memo(sz, 0);
  std::vector<int> prev(sz, -1);
  memo[0] = 1;
  int best_end = 0;
  int max_length = std::numeric_limits<int>::min();
  for (auto i = 1; i < sz; ++i) {
    for ( auto j = 0; j < i ; ++j) {
      if (s[j] < s[i] && memo[i] < memo[j] + 1) {
        memo[i] = memo[j] + 1;
        prev[i] = j;
      }
    }
    if(memo[i] > max_length) {
      best_end = i;
      max_length = memo[i];
    }
  }

  // create results
  std::vector<int> results;
  results.reserve(v.size());
  auto current = best_end;
  while (current != -1) {
    results.push_back(s[current]);
    current = prev[current];
  }
  std::reverse(results.begin(), results.end());
  return results;
}

deleted 6 characters in body

Source Link

edited Oct 31, 2015 at 22:37

bjackfly

3.3k
2
30
42

The following C++ implementation includes also some code that builds the actual longest increasing subsequence using an array called prev.

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();
    
    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(s.size()sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

The following C++ implementation includes also some code that builds the actual longest increasing subsequence using an array called prev.

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();
    
    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(s.size(), 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

The following C++ implementation includes also some code that builds the actual longest increasing subsequence using an array called prev.

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();
    
    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

added 1 character in body

Source Link

edited Aug 29, 2015 at 22:34

nbro

16k
34
122
219

Loading

added 225 characters in body

Source Link

edited Aug 29, 2015 at 21:34

nbro

16k
34
122
219

Loading

Source Link

answered Oct 28, 2013 at 16:10

bjackfly

3.3k
2
30
42

Loading

Collectives™ on Stack Overflow

Return to Answer