Code tìm tổng dãy con có tổng lớn nhất bị chạy quá thời gian

#1

Đề bài : Tìm tổng lớn nhất của dãy con không liên tiếp(hai phần tử của dãy con không được liền kề).
VD : 5 5 10 100 10 5 => output: 110 (5 + 100 + 5)

code em làm ra nhưng bị quá thời gian, anh/chị có ý tưởng gì tối ưu hóa gợi ý cho em với, em cảm ơn.

int main() {
    int test;
    std::cin>>test;
    while(test--) {
        int n;
        std::cin>>n;
        int a[n], sum[n];
        for(int i=0; i<n; i++) std::cin>>a[i];
        sum[0] = a[0];
        sum[1] = a[1];
        int best = std::max(sum[1], sum[0]);
        for(int i=2; i<n; i++) {
            for(int j=0; j<i-1; j++) {
                sum[i] = std::max(a[i], sum[j] + a[i]);
            }
            best = std::max(sum[i], best);
        }
        std::cout<<best<<std::endl;
    }
    return 0;
}
#2

Thực ra bạn chỉ cần quan tâm đến sum[i-2] và sum[i-3] vì sum[i-4] + a[i-2] <= sum[i-2] (theo định nghĩa)

3 Likes
#3
  1. Bạn đăng đề bài thiếu scope, mảng này bao nhiêu phần tử? cái này cũng có thể ảnh hưởng đến sự lựa chọn giải pháp
  2. Bạn không giải thích ý tưởng của mình khi viết đoạn code đó thì ai biết bạn nghĩ gì
    Trông sơ qua thì đoạn này có vấn đề sum[i] = std::max(a[i], sum[j] + a[i]);
    ví dụ có mảng a: 5 2 4 7
    sẽ được mảng sum: 5 2 9 9
    trong khi đáp án cuối cùng phải là 5 + 7 = 12
    sửa lại sum[i] = std::max(sum[i], sum[j] + a[i]); tất nhiên là khởi tạo mảng sum = 0 hết cho nó có giá trị để so sánh. cũng chưa chắc là đúng chưa, nhưng trước mắt là vậy
    mà có như vậy thì cũng quá thời gian mà thôi
    => bạn vừa bị chạy quá thời gian mà còn bị sai nữa

Với bài này nhìn qua thì dùng quy hoạch động, độ phức tạo O(n)
Giải pháp như sau
Ở mảng a, sẽ có những phần tử “được lấy” để tính tổng, và những phần tử “không được lấy”
như vậy mới mỗi phần tử ở vị trí i thì ta cần đặt câu hỏi, lấy thì sao, không lấy thì sao? kết quả tốt nhất nếu lấy, kết quả tốt nhất nếu không lấy
=> cần mảng để lưu kết quả khi xét phần tử r[2][n],
với r[0][i] là kết quả tốt nhất khi không lấy phần tử i
với r[1][i] là kết quả tốt nhất khi có lấy phần tử i
(khi xét mảng từ đầu tới i)

quy hoạch động thì có 2 cái cốt lõi

  1. khởi tạo
    r[0][0] = 0; // mới xét có thằng đầu tiên mà không lấy thì kết quả khi không lấy là 0 thôi
    r[1][0] = a[0]; // tương tự, kết quả là a[0]
  2. công thức truy hồi (với i > 0), như ở trên có nói, với mỗi phần tử i, thì ta có thể lấy hoặc không lấy
  • nếu không lấy phần tử i (tính r[0][i]): thì phần tử thứ i-1 lấy hay không lấy cũng được, chỉ việc chọn cách tốt hơn tính tới bước trước
    r[0][i] = max(r[0][i-1], r[1][i-1])
  • nếu lấy phần tử i (tính r[1][i]): lúc này không được tự do nữa, bắt buộc không được lấy phần tử i-1
    r[1][i] = a[i] + r[0][i-1]

đáp án cuối cùng là max(r[0][n-1], r[1][n-1]) (index start at 0)

p/s: thông thường bài như này mình sẽ ignore, nhưng loại bài này là điển hình của giải thuật quy hoạch động nên cũng muốn góp 1 câu trả lời, hy vọng sẽ giúp được gì đó
bài này còn có thể không dùng mảng (bỏ luôn cả mảng a dùng để nhập), bạn hứng thú thì tự tối ưu code thêm

5 Likes
#4

Thớt chọn sum[i] := tổng lớn nhất đã lấy a[i] rồi. Tức là chỉ cần mảng [1].

#5

dùng sum[i] là tổng lớn nhất khi có i, vậy lấy i thì đoạn trước lấy như nào? chi phí để tìm sum[i]?

#6

Với dãy a_n không âm thì ta định nghĩa

S_i = \begin{cases} 0,\ i = 0\\ a_1,\ i = 1\\ a_2,\ i = 2\\ max(\{S_j, j \leq i-2\}) + a_i,\ i \ge 3 \end{cases}

Như vậy S_{i-2} \leq S_{i} - a_{i-2} \Rightarrow S_{i-2} \leq S_{i}
Vì vậy chỉ cần tìm max(S_{i-3},\ S_{i-2}).

2 Likes
#7

đáp án này cũng đúng
nhưng tôi có góp ý thế này

thay vì bắt bẻ đáp án của người khác (cả khi đúng?) thì bạn nên có những comment xây dựng hơn, hoặc đưa ra những ý tưởng được mô tả bằng lời rồi sau đó mới đính kèm công thức chứ đừng comment kiểu cộc lốc như sách giải như vậy

  1. tôi dùng mảng để mô tả ý tưởng, không có nghĩa là phải dùng mảng để viết code. Bài này nếu tôi viết code, đâu đó chỉ cần vài cái biến mà thôi, chẳng cần mảng gì ở đây cả, cả mảng a cũng không cần, nhập tới đâu tính tới đó, nên thực tế chỉ cần một biến a duy nhất để nhập. Vậy thì giải pháp của bạn có gì tốt hơn mà phải reply mà sửa?
  2. Với những bài như thế này, người code cũng là người tự giác biết code chứ không post đề mà đi hỏi, nên chỉ cần đưa ra ý tưởng là họ có thể tự phát triển được. Chứ chỉ cái công thức viết chỉnh chu nhìn có vẻ đẹp, nhưng mà không có mô tả chi tiết thì giá trị nó cũng không được bao nhiêu
  3. Tôi không rảnh để gõ code (bài này với python tính cả nhập xuất chắc chưa tới chục dòng code). Tôi cũng không rảnh để nghiên cứu cách gõ công thức cho nó đẹp trên này. Nhưng nói về thảo luận ý tưởng thì tôi cũng khá rảnh và thích thú. Cốt lõi cũng chỉ là giải thuật. Nếu bạn muốn thể hiện bản thân, thì nó không nằm ở việc bạn bắt bẻ được ai, mà là giá trị của những comment của bạn. Có thể bạn góp ý về thiếu sót của người ta khiến bạn nghĩ mình giỏi, nhưng chắc gì người ta không biết những cái đó?
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?