Follow us on...
Follow us on Twitter Follow us on Facebook Watch us on YouTube

Tuyển chuyên viên tin tức VN-Zoom 2014

Tìm HD - Phần mềm tìm và xem phim HD miễn phí

Hoãn tổ chức offline VN-Zoom 8 năm tại TP HCM

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

Tài trợ VNZ Siêu phẩm Tân Kiếm Thế chibi 3D mới

Tuyển BQT VN-Zoom
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.510
    Cảm ơn
    37
    Điểm
    618/556 bài viết
    VR power
    7

    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
    28
    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
    688
    Cảm ơn
    52
    Điểm
    195/164 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
    28
    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
  •