Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: trích từ dãy con các ptử ltiếp tính tổng abs=t1 và tổng thương=t2 để t1+t2 max.

  1. #1
    Ngày gia nhập
    04 2012
    Bài viết
    1

    Question trích từ dãy con các ptử ltiếp tính tổng abs=t1 và tổng thương=t2 để t1+t2 max.

    Cho dãy số nguyên A=(a1,a2,....,an) trong do' |ai|<=10^9, 1<=n<=1000. Từ dãy này người ta trích ra dãy con các phần tử liên tiếp nhau, tính t1 là tổng giá trị tuyệt đối các phần tử của dãy con, t2 là tổng các phần tử của dãy con này, sau đó tính t1+t2. Hãy xác định giá trị t1+t2 lớn nhất có thể nhận được.
    VÍ Dụ A=(-3,5,-10,8,-2) Ta có thể trích ra dãy con (5,-10,8)
    ta có (|5|+|-10|+|8|)+(5+(-10)+8)=26


    Mọng mọi người giúp đỡ. Vì là người mới nhập môn nên nếu có thể các bạn cung cấp cho mình giải thuật của bài toán này để có thể hiểu rõ. Thanks

  2. #2
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    - Dùng QHĐ
    - Goị f[i][j] là giá trị lớn nhất của hàm F khi xét đến số thứ i và có j số được chọn. Kết quả là f[n][n]
    - Khi đó:
             + f[k][0]=f[k][k+1]=-oo (trừ vô cực) với 1<=k<=n
             + f[0][0]=0
    => f[i][j]= max (a[i]+abs(a[i]) + f[i-1][j-1], f[i][j-1])

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  3. #3
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Mình nhầm rồi, bài của mình là các phần tử ko liên tiếp, các phần tử liên tiếp thì đơn giản hơn

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  4. #4
    Ngày gia nhập
    04 2012
    Bài viết
    1

    bạn có thể nói rõ hơn giúp mình không ???

  5. #5
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Tổng trị tuyệt đối đem cộng tổng bình thường thì kết quả là 2 lần tổng các trị dương.
    Lô gíc quá dễ hiểu, khi đem t1 cộng t2 thì các trị âm tự động cắt trị tuyệt đối của nó hết.

    Như vậy giá trị lớn nhất có thể được của t1+t2 là 2 lần tổng các giá trị dương trong mảng.

    Nếu bài toán bắt tìm dãy con này thì nó là dãy chính trừ đi các trị âm và zero nếu có ở hai đầu.

Các đề tài tương tự

  1. Bài tập C++ trích từ dãy con các ptử ltiếp tính tổng abs=t1 và tổng thương=t2 để t1+t2 max.
    Gửi bởi huytrinh1408 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 17-04-2012, 07:47 PM
  2. Bài tập C trích từ dãy con các ptử ltiếp tính tổng abs=t1 và tổng thương=t2 để t1+t2 max.
    Gửi bởi huytrinh1408 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 17-04-2012, 07:42 PM

Quyền hạn của bạn

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