Follow us on...
Follow us on Facebook

VN-Zoom.com chung tay vì Cộng đồng

Kaka - ứng dụng hát Karaoke trên mobile

Tuyển Mod Mobile diễn dàn Vn-Zoom.com 2014

Chiêm ngưỡng BaoMoi đẹp "tuyệt diệu" trên Windows Phone

Vui thể thao quà ý nghĩa

Toàn cảnh Vn-Zoom tham gia họp báo Asus Zenfone
kết quả từ 1 tới 5 trên 5
  1. #1
    tiendung1st's Avatar
    tiendung1st vẫn chưa có mặt trong diễn đàn Gà Con
    Tham gia
    Sep 2012
    Bài
    1
    Cảm ơn
    0
    Điểm
    0/0 bài viết
    VR power
    0

    Thumbs up Tìm dãy con tăng dần có tổng lớn nhất! Pro giúp em với!!!

    Cho dãy số nguyên A1,A2,...,An. Tìm dãy con tăng dần có tổng lớn nhất? Nghĩ mãi mà không ra được thuật toán. Pro chỉ em với, viết hộ e đoạn code luôn nhé. Thanks.
    p/s: PASCAL nhé.
    Thay đổi nội dung bởi tiendung1st; 28-08-2013 lúc 22:47.

  2. #2
    programmer2010's Avatar
    programmer2010 vẫn chưa có mặt trong diễn đàn Rìu Chiến Chấm
    Tham gia
    Feb 2010
    Bài
    2.390
    Cảm ơn
    38
    Điểm
    588/523 bài viết
    VR power
    0

    Default

    sum[1]=A[1], sum[i]=max(sum[i-1]+a[i],sum[i-1],a[i]) nếu A[i]>A[i-1] và ngược lại bằng sum[i-1].

  3. #3
    chophienmet's Avatar
    chophienmet vẫn chưa có mặt trong diễn đàn Búa Gỗ Đôi
    Tham gia
    Aug 2013
    Bài
    29
    Cảm ơn
    2
    Điểm
    5/5 bài viết
    VR power
    0

    Default

    Có 1 sol O(n^3) như sau for dau, for cuoi : check đoạn đầu -> cuối kia có phải dãy tăng hay không, nếu có thì cập nhật kết quả = max( kq, tổng từ dau -> cuối)
    Sol O(n^2) thì nâng cấp từ sol n^3 For dau, for cuối, trong cái for cuối thì check dãy tăng luôn, nếu vi phạm điều kiện tăng thì break
    Sol O(n) thì khá phức tạp, khởi tạo mảng sum như #2 và dùng for tuyến tính để kiểm tra

  4. #4
    lamdetien36's Avatar
    lamdetien36 vẫn chưa có mặt trong diễn đàn Rìu Vàng
    Tham gia
    Jun 2013
    Bài
    724
    Cảm ơn
    53
    Điểm
    219/184 bài viết
    VR power
    0

    Default

    Trích chophienmet View Post
    Có 1 sol O(n^3) như sau for dau, for cuoi : check đoạn đầu -> cuối kia có phải dãy tăng hay không, nếu có thì cập nhật kết quả = max( kq, tổng từ dau -> cuối)
    Sol O(n^2) thì nâng cấp từ sol n^3 For dau, for cuối, trong cái for cuối thì check dãy tăng luôn, nếu vi phạm điều kiện tăng thì break
    Sol O(n) thì khá phức tạp, khởi tạo mảng sum như #2 và dùng for tuyến tính để kiểm tra
    Dãy con <=> gồm các phần tử không liền kề (thường là thế )
    Như vậy check đoạn [đầu; cuối] là dãy tăng hơi khó

  5. #5
    chophienmet's Avatar
    chophienmet vẫn chưa có mặt trong diễn đàn Búa Gỗ Đôi
    Tham gia
    Aug 2013
    Bài
    29
    Cảm ơn
    2
    Điểm
    5/5 bài viết
    VR power
    0

    Default

    Trích lamdetien36 View Post
    Dãy con <=> gồm các phần tử không liền kề (thường là thế )
    Như vậy check đoạn [đầu; cuối] là dãy tăng hơi khó
    Sorry đọc k kỹ đề
    Nếu là dãy con không liền kề thì có một cách dùng BIT (binary index tree) cũng khá phức tạp mình cũng ngại code
    Có thể mình hơi phức tạp hóa vấn đề 1 chút, mình sẽ nghĩ kỹ thêm

 

 

Tag của Đề tài này

Quyền sử dụng

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể tự sửa bài viết của mình
  •