daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Feb 17th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int maxEnvelopes(vector<pair<int, int>>& envelopes) {
  4.         if (envelopes.empty()) return 0;
  5.         sort(envelopes.begin(), envelopes.end());
  6.        
  7.         vector<int> dp(envelopes.size(), 1);
  8.        
  9.         for (int i = 1; i < envelopes.size(); ++i) {
  10.             for (int j = 0; j < i; ++j) {
  11.                 if (envelopes[j].first < envelopes[i].first &&
  12.                     envelopes[j].second < envelopes[i].second)
  13.                      dp[i] = max(dp[i], dp[j] + 1);
  14.             }
  15.         }
  16.        
  17.         return *max_element(dp.begin(), dp.end());
  18.     }
  19. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top