• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Conference Contributions
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Engineering
    • Engineering: Conference Contributions
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    Statistics

    View Usage Statistics

    Algorithms for K disjoint maximum subarrays

    Thumbnail
    View/Open
    12602250_Main.pdf (391.7Kb)
    Author
    Sung, S.B.
    Takaoka, T.
    Date
    2006
    Permanent Link
    http://hdl.handle.net/10092/112

    The maximum subarray problem is to find the array portion that maximizes the sum of array elements in it. For K disjoint maximum subarrays, Ruzzo and Tompa gave an O(n) time solution for one-dimension. This solution is, however, difficult to extend to twodimensions. While a trivial solution of O(Kn³) time is easily obtainable for two-dimensions, little study has been undertaken to better this. We first propose an O(n + K log K) time solution for one-dimension. This is equivalent to Ruzzo and Tompa’s when order is considered. Based on this, we achieve O n³+Kn² log n) time for two-dimensions. This is cubic time when K ≤ n / log n.

    Subjects
    Fields of Research::280000 Information, Computing and Communication Sciences::280300 Computer Software
    Collections
    • Engineering: Conference Contributions [1816]
    Rights
    http://library.canterbury.ac.nz/ir/rights.shtml

    UC Research Repository
    University Library
    University of Canterbury
    Private Bag 4800
    Christchurch 8140

    Phone
    364 2987 ext 8718

    Email
    ucresearchrepository@canterbury.ac.nz

    Follow us
    FacebookTwitterYoutube

    © University of Canterbury Library
    Send Feedback | Contact Us