Advertisement
HjHimansh

Sid -> Switching Length

Aug 30th, 2020
1,479
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. //find the longest switching array.
  6.  
  7. typedef struct{
  8.     int lengthMaxSwitching;
  9.     int oddElem;
  10.     int evenElem;
  11. } rt;
  12.  
  13. rt h_solution(vector<int> &A, int index, unordered_map<int, rt> &memo){
  14.     //returns maximum switching array ending at index;
  15.     rt to_return;
  16.    
  17.     if(memo.count(index)){
  18.         return memo[index];
  19.     }
  20.    
  21.     if(index == 0){
  22.         to_return.lengthMaxSwitching = 1;
  23.         to_return.oddElem = A[index];
  24.         to_return.evenElem = INT_MAX;
  25.         memo[index] = to_return;
  26.         return to_return;
  27.     }
  28.     if(index == 1){
  29.         to_return.lengthMaxSwitching = 2;
  30.         to_return.oddElem = A[0];
  31.         to_return.evenElem = A[1];
  32.         memo[index] = to_return;
  33.         return to_return;
  34.     }
  35.    
  36.     rt L = h_solution(A, index-1, memo);
  37.     if(L.lengthMaxSwitching % 2 == 0){
  38.         //i.e current element will be at odd position
  39.         if(A[index]==L.oddElem){
  40.             to_return = L;
  41.             to_return.lengthMaxSwitching+= 1;
  42.             memo[index] = to_return;
  43.             return to_return;
  44.         }
  45.         else{
  46.             to_return.lengthMaxSwitching = 2;
  47.             to_return.evenElem = A[index];
  48.             to_return.oddElem = A[index-1];
  49.             memo[index] = to_return;
  50.             return to_return;
  51.         }
  52.     }
  53.     else{
  54.         //ie current element will be at even position
  55.         if(A[index]==L.evenElem){
  56.             to_return = L;
  57.             to_return.lengthMaxSwitching += 1;
  58.             memo[index] = to_return;
  59.             return to_return;
  60.         }
  61.         else{
  62.             to_return.lengthMaxSwitching = 2;
  63.             to_return.evenElem = A[index];
  64.             to_return.oddElem = A[index-1];
  65.             memo[index] = to_return;
  66.             return to_return;
  67.         }
  68.     }
  69. }
  70.  
  71. int solution(vector<int> &A){
  72.     if(A.size()<=2) return A.size();
  73.    
  74.     unordered_map<int, rt> memo;
  75.    
  76.     int answer = 0;
  77.     for(int i=0; i<A.size(); i++){
  78.         answer = max(answer, h_solution(A, i, memo).lengthMaxSwitching);
  79.     }
  80.     return answer;
  81. }
  82.  
  83. int main() {
  84.     vector<int> sample = {7,-5, -5, -5, 7, -1, 7};
  85.     cout << solution(sample) << endl;
  86.     return 0;
  87. }
Advertisement
RAW Paste Data Copied
Advertisement