khi các giá trị có thể âm thì mình chỉ cần tạo ra 2 biến , 1 biến dùng lưu tổng giá trị lớn nhất của dãy con THỎA MÃn yêu cầu đề bài nằm phía trước ( tính đến vị trí i - 2) , 1 biến lưu tổng giá trị lớn nhất tính của dãy con THỎA MÃN tính đến vị trí i - 3 , cuối cùng tại mỗi vị trí i công việc của ta là lấy max , đồng thời cập nhật giá trị cho 2 biến phía trên để xíu nữa khi tới vị trí i+1 , mình có cái để sử dụng
có cái mình k hiểu là, ví dụ trg vid là 6 chỉ sao lại chọn 3 và 4 ạ? và tại sao lại k chọn 2 vì 2 đấy vẫn có thể lớn hơn 3 và 4 mà? trg vid có nói là 2 luôn bé hơn nhma mình k rõ cái lý do ấy ạ
Bạn để ý trong video mình có nói là các số a[i] luôn DƯƠNG , khi đó dp ở vị trí 4 chắc chắn lớn hơn dp ở vị trí 2, bởi vì dp 4 được tạo từ a4+ max(dp2,dp1), xảy ra 2 trường hợp , 1 là dp2 lớn hơn dp1, khi đó dp4= a4+ dp2, hiển nhiên dp4 chắc chắn lớn hơn dp2
Trường hợp còn lại dp4 được tạo thành từ a4+ dp1, điều này chứng tỏ dp2 < dp1( do nhỏ hơn nên mới không được chọn) =>> thằng dp2 sẽ k được tham gia vào phép tính dp6
Mình bổ sung thêm , mình đã định nghĩa dp[i] là dãy con thoả mãn lớn nhất từ đầu tới vị trí i ,sau đó là trường hợp cơ sở qhd , thử hỏi với i= 2 và i =4 dp nào sẽ lớn hơn ?
Nếu dp2 > dp4 thì mình sẽ phát biểu là : dãy con lớn nhất thoả mãn từ đầu tới vị trí 2 sẽ lớn hơn dãy con lớn nhất thoả mãn từ đầu tới vị trí 4, bạn thấy có lí hay vô lí
hay lắm ạ
khi các giá trị có thể âm thì mình chỉ cần tạo ra 2 biến , 1 biến dùng lưu tổng giá trị lớn nhất của dãy con THỎA MÃn yêu cầu đề bài nằm phía trước ( tính đến vị trí i - 2) , 1 biến lưu tổng giá trị lớn nhất tính của dãy con THỎA MÃN tính đến vị trí i - 3 , cuối cùng tại mỗi vị trí i công việc của ta là lấy max , đồng thời cập nhật giá trị cho 2 biến phía trên để xíu nữa khi tới vị trí i+1 , mình có cái để sử dụng
có cái mình k hiểu là, ví dụ trg vid là 6 chỉ sao lại chọn 3 và 4 ạ? và tại sao lại k chọn 2 vì 2 đấy vẫn có thể lớn hơn 3 và 4 mà? trg vid có nói là 2 luôn bé hơn nhma mình k rõ cái lý do ấy ạ
Bạn để ý trong video mình có nói là các số a[i] luôn DƯƠNG , khi đó dp ở vị trí 4 chắc chắn lớn hơn dp ở vị trí 2, bởi vì dp 4 được tạo từ a4+ max(dp2,dp1), xảy ra 2 trường hợp , 1 là dp2 lớn hơn dp1, khi đó dp4= a4+ dp2, hiển nhiên dp4 chắc chắn lớn hơn dp2
Trường hợp còn lại dp4 được tạo thành từ a4+ dp1, điều này chứng tỏ dp2 < dp1( do nhỏ hơn nên mới không được chọn) =>> thằng dp2 sẽ k được tham gia vào phép tính dp6
Cả 2 trường hợp đều chứng tỏ dp2 không thể được chọn , dp3 và dp4 sẽ bao quát hơn
Mình bổ sung thêm , mình đã định nghĩa dp[i] là dãy con thoả mãn lớn nhất từ đầu tới vị trí i ,sau đó là trường hợp cơ sở qhd , thử hỏi với i= 2 và i =4 dp nào sẽ lớn hơn ?
Nếu dp2 > dp4 thì mình sẽ phát biểu là : dãy con lớn nhất thoả mãn từ đầu tới vị trí 2 sẽ lớn hơn dãy con lớn nhất thoả mãn từ đầu tới vị trí 4, bạn thấy có lí hay vô lí