fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. // Binary search (note boundaries in the caller)
  5. int CeilIndex(std::vector<int>& v, int l, int r, int key)
  6. {
  7. 	while (r - l > 1) {
  8. 		int m = l + (r - l) / 2;
  9. 		if (v[m] >= key)
  10. 			r = m;
  11. 		else
  12. 			l = m;
  13. 	}
  14.  
  15. 	return r;
  16. }
  17.  
  18. int LongestIncreasingSubsequenceLength(std::vector<int>& v)
  19. {
  20. 	if (v.size() == 0)
  21. 		return 0;
  22.  
  23. 	std::vector<int> tail(v.size(), 0);
  24. 	int length = 1; // always points empty slot in tail
  25.  
  26. 	tail[0] = v[0];
  27. 	for (size_t i = 1; i < v.size(); i++) {
  28.  
  29. 		// new smallest value
  30. 		if (v[i] < tail[0])
  31. 			tail[0] = v[i];
  32.  
  33. 		// v[i] extends largest subsequence
  34. 		else if (v[i] > tail[length - 1])
  35. 			tail[length++] = v[i];
  36.  
  37. 		// v[i] will become end candidate of an existing
  38. 		// subsequence or Throw away larger elements in all
  39. 		// LIS, to make room for upcoming greater elements
  40. 		// than v[i] (and also, v[i] would have already
  41. 		// appeared in one of LIS, identify the location
  42. 		// and replace it)
  43. 		else
  44. 			tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
  45. 	}
  46.  
  47. 	return length;
  48. }
  49.  
  50. int main()
  51. {
  52. 	std::vector<int> v{ 1,2,2,3,4};
  53. 	std::cout << "Length of Longest Increasing Subsequence is "
  54. 			<< LongestIncreasingSubsequenceLength(v) << '\n';
  55. 	return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 5456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length of Longest Increasing Subsequence is 4
https://ideone.com/j1VfuS
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!