Maximum sum such that no two elements are adjacent

algorithm
java

(mmmm) #1

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.


(Hoang) #2

Đề bài là tìm tổng lớn nhất trong đó 2 phần tử là không kề nhau


(mmmm) #3

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


(Nguyễn Đình Anh) #4

Đề bài là tìm tổng lớn nhất của các số không liền kề trong mảng. :slight_smile:


VD1: 3, 2, 7, 10
Ở đây có các số không liền kề nhau là:

  • 3, 7 ==> Tổng là 10
  • 2, 10 ==> Tổng là 12
  • 3, 10 ==> Tổng là 13

Vì 13 là số lớn nhất nên kết quả ở đây là 13.

Tương tự như vậy ở VD2 nhé :slight_smile:


(Nguyễn Đình Anh) #5

Không phải bạn ạ, 110 là tổng của 100 + 5 + 5 mà @@


(rogp10) #6

Vậy thì [2, 5, 5, 4] ra 5 + 4 = 9 luôn :smiley: 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 :smiley: chắc O(n).


(Hung) #7

Định giải mà search phát ra cái đề và bài giải luôn


(mmmm) #8

thì đừng search :joy: 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


(rogp10) #9

Mà mình vừa drop hint rồi :smiley:

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]


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?