Maximum sum such that no two elements are adjacent

#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.

#2

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

#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

#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:

1 Like
#5

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

1 Like
#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. O(n) chắc chắn.

3 Likes
#7

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

2 Likes
#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

3 Likes
#9

Chỉ đúng với số dương:

    u[0] = a[0]; // có a[i]
    v[0] = 0; // không có a[i] 
    v[i] = max(u[i-1], v[i-1]); // thêm a[i-1] hay không?
    u[i] = v[i-1] + a[i];
    return max(u[n], v[n]);

O(1) mem.

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