Guest User

Untitled

a guest
Aug 20th, 2019
66
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<limits.h>
  2. void DFS(vector<int> &A, vector<int> &B, int &res, vector<int> tmp, int nextIndex) {
  3.  
  4. int curIndex = tmp.back();
  5. if (!(A[curIndex] <= A[nextIndex] && A[nextIndex] <= B[curIndex]) &&
  6. !(A[nextIndex] <= A[curIndex] && A[curIndex] <= B[nextIndex])) {
  7. tmp.push_back(nextIndex);
  8. }
  9.  
  10. res = max(res, (int)tmp.size());
  11. for (int i = nextIndex + 1; i < (int)A.size(); i++) {
  12. DFS(A, B, res, tmp, i);
  13. }
  14. }
  15.  
  16. int solution(vector<int> &A, vector<int> &B) {
  17. // write your code in C++14 (g++ 6.2.0)
  18. int size = (int)A.size();
  19.  
  20. vector<int> tmp;
  21. int res = 0;
  22. for (int i = 0; i < (int)A.size() - 1; i++) {
  23. tmp.push_back(i);
  24. DFS(A, B, res, tmp, i + 1);
  25. tmp.pop_back();
  26. }
  27.  
  28. return size == 1 ? 1: res;
  29. }
RAW Paste Data