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

Bóc hộp Wiko Getaway giá rẻ, dáng đẹp và Selfie thì cực Chất

Gameshow “Ai Là Triệu Phú” trên VTV đang chờ đón bạn – Tải ngay!

Reviews hay rinh note 4, galaxy V được vi vu Hàn Quốc

Mời anh em tham gia Vn-zoom support team

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

Tin tức công nghệ sản phẩm mới
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
    VZD
    0
    Cảm ơn
    0
    Điểm
    0/0 bài viết

    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.678
    VZD
    227
    Cảm ơn
    39
    Điểm
    666/602 bài viết

    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
    VZD
    0
    Cảm ơn
    2
    Điểm
    5/5 bài viết

    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
    VZD
    0
    Cảm ơn
    52
    Điểm
    196/164 bài viết

    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
    VZD
    0
    Cảm ơn
    2
    Điểm
    5/5 bài viết

    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
  •