[C++] Data structures and their common operators

	vector	stack	queue	Deque (Double ended queue)	Priority_queue
Access	x=v.front() x=v.back()	x=s.top()	x=q.front()	x=dq.front() x=dq.back()	x=pq.top()
Add	v.insert(itr, x) v.push_back(x) v.emplace(itr, x) v.emplace_back(x)	s.emplace(x) s.push(x)	q.emplace(x) q.push(x)	dq.emplace(itr, x) dq.emplace_back(x) dq.emplace_front(x) dq.push_back(x) dq.push_front(x) dq.insert(itr,x)	pq.emplace(x) pq.push(x)
Remove	v.clear() v.erase(itr) v.pop_back()	s.pop()	q.pop()	dq.clear() dq.erase(itr) dq.pop_back() dq.pop_front()	pq.pop()
Check empty	v.empty()	s.empty()	q.empty()	dq.empty()	pq.empty()
Check size	x=v.size()	x=s.size()	x=q.size()	dq.size()	pq.size()

Vector vs. Deque:

Both vector and deque provide a very similar interface, but internally they work in quite different ways: vector uses a single array that needs occasionally re-allocation for growth; deque has its elements scattered in different chunk of storage, with the container keeping the necessary information for direct accesses to any element in constant time - through iterators.

[LeetCode] Maximum Subarray

Problem Statement (link):

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Analysis:
Suppose we scan from left to right, each element could either be counted in the max-sum subarray, or not. If we use an array to store this information, we probably could solve the problem in O(n) time.

Thus, the idea is to use DP to solve the problem. Specifically, the DP array stores the maximum sum we have so far if we count the current element in. In addition, we use an integer to store the maximum sum we have so far.

Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n==0) return 0;
        int maxSum=INT_MIN; // max sum so far
        vector<int> dp(n+1);  // dp[i+1]: the maxSum of subarray which ends with A[i];
        dp[0]=0;
        for (int i=0; i<n; i++) {
            if (dp[i]<0) dp[i+1]=A[i];
            else dp[i+1]=dp[i]+A[i];
            maxSum=max(maxSum, dp[i+1]);
        }
        return maxSum;
    }
};