some interesting code
Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example1:
1 2 3
 Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

Example2:
1 2
 Input: "cbbd" Output: "bb"

solution
Dynamic Programming
1 2 3 4 5 6 7 8
 define P(i, j) = if S[i, j] is a palindrome ? true : false
Recursive: P(i, j) = (P(i+1, j1) and S[i] == S[j])
Base: P(i,i) = true P(i, i+1) = (S[i] == S[i+1])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 class Solution { public: string longestPalindrome(string s) { int size = s.size(); if (size < 2) return s; bool dp[size][size]; int maxLen = 1; int pos = 0; for (int j = 0; j < size; ++j) { dp[j][j] = true; for (int i = 0; i < j; ++i) { if (j == i+1) { dp[i][j]= (s[i] == s[j]); } else { dp[i][j] = ((s[i] == s[j]) && dp[i+1][j1]); } int len = j  i + 1; if (len > maxLen && dp[i][j]) { maxLen = len; pos = i; } } } return s.substr(pos, maxLen); } };

Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
1 2
 Input: [3,2,1,5,6,4] and k = 2 Output: 5

Example 2:
1 2
 Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
 class Solution { public: template<typename Comparator> int partition(vector<int>& nums, int left, int right, Comparator cmp) { int pivot = nums[left]; swap(nums[left], nums[right]); int pos = left; for (int i = left; i < right; ++i) { if (cmp(nums[i], pivot)) { swap(nums[i], nums[pos++]); } } swap(nums[pos], nums[right]); return pos; } int findKthLargest(vector<int>& nums, int k) { int left = 0; int right = nums.size()  1; while (left <= right) { int idx = partition(nums, left, right, greater<>()); if (idx == k  1) return nums[idx]; else if (idx < k  1) left = idx + 1; else right = idx  1; } return 1; } };

OR
1 2 3 4 5 6 7
 class Solution { public: int findKthLargest(vector<int>& nums, int k) { nth_element(nums.begin(), nums.end()k, nums.end()); return nums[nums.size()k]; } };
