Cho một mảng gồm các số nguyên hãy tìm tổng lớn nhất của tất cả các chuỗi con mà không có 2 phần tử nào đứng cạnh nhau trong chuỗi con đó.
Với arr = [1,4,1] thì đầu ra của MaximumNonAdj(arr) = 4 . Các chuỗi con không có 2 phần tử nào liền kề nhau là (1), (4), (1), (1,1) trong đó chuỗi có tổng lớn nhất là 4.
Cho e hỏi công thức của em như thế này thì sai ở đâu vậy ạ
int MaximumNonAdj(std::vector<int> arr)
{
int Max=*max_element(arr.begin(), arr.end());
int *f = new int [arr.size() + 1];
f[0]=arr[0];
f[1]=max(f[0], arr[1]);
for(int i=2;i<arr.size();i++)
{
f[i]=max(max(f[i-2]+arr[i], f[i-1]), f[i-2]);
}
return max(Max,*max_element(f, f+arr.size()));
}
ý tưởng của e là xét tới vị trí i thì f[i] là max của f[i-2] nếu lấy thì + thêm arr[i] nếu ko thì ko cộng
và max của f[i-1] và ko lấy arr[i]
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?