01/10/2018, 16:35
Maximum sum such that no two elements are adjacent
Mình có đề dưới đây, có phải là tìm tổng lớn nhất của 2 số ko liền kề nằm trong mảng không ạ. Sao cái ví dụ thứ 2 lại là có 3 số nhỉ?
Maximum sum such that no two elements are adjacent
Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.
Bài liên quan
Đề bài là tìm tổng lớn nhất trong đó 2 phần tử là không kề nhau
Bạn cho mình hỏi thêm với
Input : arr[] = {5, 5, 10, 100, 10, 5}
Output : 110
vậy số 5 xuất hiện 3 lần thì cho là 1 số thôi hã bạn
Đề bài là tìm tổng lớn nhất của các số không liền kề trong mảng.
VD1:
3, 2, 7, 10Ở đây có các số không liền kề nhau là:
Vì 13 là số lớn nhất nên kết quả ở đây là 13.
Tương tự như vậy ở VD2 nhé
Không phải bạn ạ, 110 là tổng của 100 + 5 + 5 mà @@
Vậy thì [2, 5, 5, 4] ra 5 + 4 = 9 luôn hai số 5 mà.
Khi đã chọn một số thì không thể chọn hai bên nó được nữa. Giờ làm với mảng số (nguyên) dương trước chắc O(n).
Định giải mà search phát ra cái đề và bài giải luôn
GeeksforGeeks – 26 Nov 09
Maximum sum such that no two elements are adjacent - GeeksforGeeks
Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be… Read More »
thì đừng search mình tưởng thuật toán thì nghĩ ko ra mới search chứ, có ai bắt search trước khi làm đâu
Mà mình vừa drop hint rồi
Vậy bài này cũng là QHĐ.
[spoiler]u[0] = a[0] /* có i /
v[0] = 0 ./ không có i */
v[i] = max(u[i-1], v[i-1])
u[i] = v[i-1] + a[i]
: return max(u[n], v[n])
O(1) mem.[/spoiler]