Revision as of 13:56, 10 February 2023 edit Liu1126 (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 12,270 edits Adding local short description: "Problem in computer science", overriding Wikidata description "the task of finding a contiguous subarray with the largest sum in a given array of numbers" Tag: Shortdesc helper ← Previous edit		Revision as of 02:11, 26 February 2023 edit undo 76.26.248.74 (talk) →Complexity Tag: Reverted Next edit →
Line 149: ===Complexity=== Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple/trivial example of [[dynamic programming]]. The runtime complexity of Kadane's algorithm is <math>O(n)</math>.{{sfn\|Bentley\|1989\|p=74}}{{sfn\|Gries\|1982\|p=211}}

Maximum subarray problem: Difference between revisions