# Algorithm
## Knapsack
Low efficient solution
Dynamic programming

https://leetcode.com/problems/coin-change/submissions/
Because in this case we tend to use larger coin, we directly substitute the smaller one with larger.

#define min(i, j) ((i) < (j) ? (i): (j))
int coinChange(int coins, int coinsSize, int amount){
    if(amount == 0) return 0;
    int dp[amount + 1];
    dp[0] = 0;
    for(int i = 1; i <= amount; ++i) dp[i] = amount + 1;
    for(int i = 1; i <= amount; ++i){
        for(int j = 0; j < coinsSize; ++j){
            if(coins[j] <= i){
                dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
            } 
        }
    }
    if(dp[amount] == amount + 1) return -1;
    return dp[amount];
    //  0 1 2 3 4 5
    //1 0 1 2
    //2 0 0 
    //5 0 0
    //    1
}

## Backtracking
make sure that the value of the target doesn't exceed the sum of other numbers.
## Kadane
Just compare the max_current to the current, and identify if the former is larger than the latter.
https://leetcode.com/problems/maximum-product-subarray/discuss/48230/Possibly-simplest-solution-with-O(n)-time-complexity
There is an example :
3 -1 2
cur 3 2 4
glo 3 2 4
When cur is equal to -1, it compare 3 + -1 to -1. It turns out to be 3 + -1. As a result, we can get the maximum value when having a negative number.
very nice . I guess a bit of more explanation would help people understand:

this is very similar to the " max cumulative sum subarray" problem. here you keep 2 values: the max cumulative product UP TO current element starting from SOMEWHERE in the past, and the minimum cumuliative product UP TO current element . it would be easier to see the DP structure if we store these 2 values for each index, like maxProduct[i],minProduct[i] .

at each new element, u could either add the new element to the existing product, or start fresh the product from current index (wipe out previous results), hence the 2 Math.max() lines.

if we see a negative number, the "candidate" for max should instead become the previous min product, because a bigger number multiplied by negative becomes smaller, hence the swap()：

int maxProduct(int A[], int n) {
    int r = A[0];
     imax/imin stores the max/min product of
     subarray that ends with the current number A[i]
    for (int i = 1, imax = r, imin = r; i < n; i++) {
        if (A[i] < 0)
           swap(imax, imin);
        imax = max(A[i], imax * A[i]);
        imin = min(A[i], imin * A[i]);
        r = max(r, imax);
    }
    return r;
}

My code:

#define max(i, j) ((i > j) ? i : j)
#define min(i, j) ((i < j) ? i : j)
#define swap(i, j) ((i)^=(j)^=(i)^=(j))
int maxProduct(int nums, int numsSize){
    int maxn, minn;
    int num = maxn = minn = nums[0];
    for(int i = 1; i < numsSize; ++i){
        if(nums[i] < 0) swap(maxn, minn);
        maxn = max(nums[i], maxn * nums[i]);
        minn = min(nums[i], minn * nums[i]);
        num = max(maxn, num);
    }
    return num;
}*

# Algorithm for C++
## map.find(key value): return its iterator
If it doesn't find the value, return map.end()
## map.erase(key value): remove the value
## std::string::npos
It is usually defined like this:
static const size_t npos = -1;

size_t startpos = string.find_first_not_of("0");
if(string::npos != startpos) 
    return sum.substr(startpos);

## string.find_first_not_of('char'): finding the element that isn't included in the string.

string str = "000011111111";
size_t startpos = str.find_first_not_of('0');
//it returns the first value that doens't equal to the element in the string.
//If there is no such a value, it will equal string::npos.

## string.substr(...)
1. string.substr(pos): from the position to the end.
2. string.substr(fistpos, secondpos): from the first position to the second position.
## vector_name.clear()
## vector_name.erase(iterator)
1. vector.erase(iterator)
2. vector.erase(iterator1, iterator2)
## unique and erase

#include<algorithm>
#include<vector>
int main() {
    vector<int> v{ 1, 1, 3, 3, 3, 10, 1, 3, 3, 7, 7, 8 };
    vector<int>::iterator it = unique(v.begin(), v.end());
    //unique will shorten the vector, and it points to the fist element that 
    //is put to the last of the vector.
    //As a result, we use erase to eliminate those elements which are put backwards.
    for (auto i : v) cout << i << " ";
    cout << "\nThe first element which is put to the last " << *it << endl;
    v.erase(it, v.end());
    for (auto i : v) cout << i << " ";
    cout << "\n" << *it << endl;
}

# implemetation in C++
## Use a class to remove and insert the element.
Note that: there is no any duplicate allowed.

#include<vector>
#include<iostream>
#include<algorithm>
#include<string>
#include<unordered_map>
using namespace std;
class store {
public:
    unordered_map<int, int>map;
    vector<int> v;
    bool insert(int value) {
        if (map.find(value) != map.end()) {
            cout << "there is dupliate\n";
            return false;
        }
        v.emplace_back(value);
        map[value] = v.size() - 1;
        return true;
    }
    bool remove(int value) {
        auto it = find(v.begin(), v.end(), value);
        if (it != v.end()) {
            v.erase(it);
            int index = map[value];
            for (auto &i : map) {
                if (i.second > index) --i.second;
            }
            map.erase(value);
            //1 2 3
            return true;
        }
        else {
            cout << "no such a element in the vector\n";
            return false;
        }
    }
    bool getindex(int value) {
        if(v.size() > 0 && map.find(value) != map.end()){
            cout << value << "'s index: " << map[value] << endl;
            return true;
        }
        else {
            cout << "no such a value in the vector\n";
            return false;
        }
    }
};

int main() {
    store s;
    string ans;
    int value;
    cout << "Input: remove, insert, getindex, show map, or show array\n";
    while (1) {
        if (getline(cin, ans)){}
        else { break; }
        if (ans == "remove") {
            cout << "input the element you want to remove\n";
            value = 0;
            cin >> value;
            s.remove(value);
        }
        else if (ans == "insert") {
            cout << "input the element you want to insert\n";
            value = 0;
            cin >> value;
            s.insert(value);
        }
        else if (ans == "show map") {
            if (s.map.size() == 0) {
                cout << "no element in the map\n";
            }
            else
                for (auto i : s.map) {
                    cout << i.first << ": " << i.second << endl;
                }
        }
        else if (ans == "show array") {
            if (s.v.size() == 0)
                cout << "no element in the vector\n";
            else{
                for (auto i : s.v) {
                    cout << i << ' ';
                }
                cout << endl;
            }
        }
        else if (ans == "getindex") {
            if (s.v.size() != 0) {
                value = 0;
                cin >> value;
                s.getindex(value);
            }
            else {
                cout << "there is no value in the vector" << endl;
            }
        }
    }
}