HackerRank‐Dynamic Programming - a920604a/leetcode GitHub Wiki

// Complete the maxSubsetSum function below.
int maxSubsetSum(vector<int> arr) {

    //  -2  1   3   -4  5
    //  0   1   3   3   8
    int n = arr.size();
    vector<int> dp(n,0);
    dp[0] = max(0,arr[0]);
    if(n==1) return dp.back();
    dp[1] = max(arr[1], dp[0]);
    for(int i=1;i<n;++i){
        dp[i] = max(arr[i] + dp[i-2], dp[i-1]);
    }
    return dp.back();
}

int maxSubsetSum(vector<int> arr) {
    //  3   7   4   6   5
    //  3   7   7   13  12  
    int n = arr.size();
    if(n==1) return arr[0];
    int r1 = arr[0], r2 = max(arr[0], arr[1]);
    for(int i=2;i<n;++i){
        int tmp = r2;
        if(r1>0) r2 = max(r2, r1+arr[i]);
        else r2 = max(r2, arr[i]);
        r1 = tmp;
    }
    return r2;
}

long candies(int n, vector<int> arr) {
    //  4   6   4   5   6   2
    //  1   1   1   1   1   1
    //  1   2   1   2   3   1
    
    //  2   4   2   6   1   7   8   9   2   1
    //  1   2   1   2   1   2   3   4   1   1
    //  
    
    vector<int> vec(n,1);
    for(int i=1;i<n;++i){
        if(arr[i] > arr[i-1]) vec[i] = vec[i-1]+1;
    }
    for(int i=n-2;i>-1;i--){
        if(arr[i] > arr[i+1] && vec[i] <= vec[i+1]) vec[i] = vec[i+1]+1;
    }
    long count =0 ;
    for(int v:vec) count+=v;
    return count;
}

string abbreviation(string a, string b) {
    //      A   B   D   E
    //   0  0   0   0   0
    // A 1  1   0   0   0    
    // b 1  1   1   0   0    
    //c  1  1   1   0   0
    //D  1  0   0   1
    //E  1              1
    
    //      A   B   C
    //      1   0   0
    //d  1  0   0   0   
    //a  1  1   
    //B  1      1
    //c  1      1   1
    //d  1      1   1

    int n = a.size() , m=b.size();
    vector<vector<bool>> dp(n+1, vector<bool> (m+1,false));
    for(int i=0;i<=n;++i) dp[i][0] = true;
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;++j){
            if(a[i-1] == b[j-1])  dp[i][j] = dp[i-1][j-1];
            else if(a[i-1] == b[j-1] || toupper(a[i-1]) == b[j-1] ) dp[i][j] = dp[i-1][j-1] || dp[i-1][j];
            else if( islower(a[i-1]) ) dp[i][j] = dp[i-1][j];
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
    return dp[n][m]?"YES":"NO";
    
}