câu trả lời tốt nhất cho việc tìm kiếm tổng tối đa có thể trong một mảng là gì

Question

Câu hỏi đặt ra là:

Tìm tổng tối đa có thể trong một mảng các số nguyên dương bằng cách chọn các yếu tố trong một cách như vậy mà không có hai yếu tố này là tiếp theo với nhau.

có một câu trả lời như thế này: nhưng những gì là câu trả lời tốt nhất cho câu hỏi này

Hãy biểu thị các mảng bằng "t" và chỉ số nó từ 0. Hãy f là một hàm để f (k) = tổng cực đại trong [0..k] subarray với các điều kiện của vấn đề. Bây giờ sử dụng lập trình năng động:

f(0) = t[0] 
f(1) = max{ t[0], t[1] } 
f(k) = max{ f(k-2) + t[k], f(k-1) } if k >= 2 

If the array has n elements we need f(n-1). 

Cảm ơn trước.

Answer 1

Giải pháp bạn đề xuất là good one.

tương tự cách tiếp cận (trang 7 here):

Hãy m[i] là tổng tối đa của bất kỳ subarray rằng kết thúc vào các yếu tố a[i] .Sau đó m[i] đơn giản max(a[i], m[i-1]+a[i]) là.

Đây là O(n).

và bạn không thể có được bất cứ điều gì dưới đây O(n) là bạn có đến thăm tất cả các mục của mảng ít nhất một lần để tính toán kết quả.

Answer 2

Vâng, tôi nghĩ rằng đây là câu trả lời hay nhất.
Vì bạn cần O (n) để đọc dữ liệu.
một thuật toán O (n) là nhanh nhất trong ký hiệu big-O.

Answer 3

public static int maxSum(int[] A){ 
    return maxSum(A,0,1); 
} 
private static int maxSum(int[] A, int x, int y){ 
    int c =0, d=0; 
    if(x<A.length){ 
     c = A[x]+maxSum(A,x+2,x+3); 
    } 
    if(y<A.length){ 
     d = A[y]+maxSum(A,y+2,y+3); 
    } 
    return c>d?c:d; 
}