Menu Close

[HackerRank] Max Array Sum

Problem

Link: https://www.hackerrank.com/challenges/max-array-sum/problem
Mô tả vắn tắt:
Cho một mảng gồm các số nguyên. Tìm tổng lớn nhất của các tập con tạo nên từ mảng ban đầu với điều kiện không có phần tử liền kề.

Solution

[Giải với Dynamic programming]

// Complete the maxSubsetSum function below.
int maxSubsetSum(vector<int> arr) {
    vector<long> maxArr(arr.size(),0);
    maxArr[0]=arr[0]>0?arr[0]:0;
    maxArr[1]= arr[1]>maxArr[0]? arr[1]:maxArr[0];
    for(size_t i=2;i<arr.size();i++){
        if(arr[i]+maxArr[i-2]>maxArr[i-1]){
            maxArr[i]=arr[i]+maxArr[i-2];
        }else{
            maxArr[i]=maxArr[i-1];
        }
    }
    return maxArr[arr.size()-1];

}

3 Comments

    • blackntt

      là 2 giá trị cơ sở của bảng chứ giá trị sum để thực hiện quy hoạch động

      • blackntt

        Nếu chỉ có 1 phần tử ở vị trí 0 thì rõ ràng thì chỉ có 1 sum là giá trị arr[0], nếu có 2 phần tử thì tổng sẽ là max của arr[0] và arr[1] (đề yêu cầu các phần tử trong tập con phải không liền nhau). Từ đó tính tiếp

Leave a Reply

Your email address will not be published. Required fields are marked *