Wednesday, September 23, 2020

Subset of non-adjacent elements with the maximum sum

int maxSubsetSum(vector<int> arr) {
    int cmax = 0, curr_plus_previous_not_adj;

    int previous_not_adj = arr[0];
    int previous_adj = max(arr[1], previous_not_adj);

    for(int i = 2; i < arr.size(); i++) {
            curr_plus_previous_not_adj = max(arr[i], arr[i] + previous_not_adj);
            cmax = max(curr_plus_previous_not_adj, previous_adj);
            previous_not_adj = previous_adj;
            previous_adj = cmax;
    }
    return cmax;
}

No comments:

Blog Archive