{
  "id": "enwiki-001365852288",
  "slug": "maximum-subarray-problem",
  "title": "Maximum subarray problem",
  "qid": "",
  "lead": "[[File:Maximum Subarray Visualization.svg|thumbnail|Visualization of how sub-arrays change based on start and end positions of a sub-array. Each colored line corresponds to a fixed starting index in the array. The leftmost point of a line represents the single-element sub-array starting at that index, and each subsequent point extends the sub-array by one element to the right. The x-coordinate of a point is the index of the last element in the sub-array, and the y-coordinate is the sum of the sub-array. In this case, the original array from which sub-arrays are taken is [2, 3, -1, -20, 5, 10]. In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. It can be solved in O(n) time and O(1) space. Formally, the task is to find indices i and j with 1 \\leq i \\leq j \\leq n , such that the sum : \\sum_{x=i}^j A[x] is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention, the sum of all values of the empty subarray is zero.) Each number in the input array A could be positive, negative, or zero.…",
  "body": "[[File:Maximum Subarray Visualization.svg|thumbnail|Visualization of how sub-arrays change based on start and end positions of a sub-array. Each colored line corresponds to a fixed starting index in the array. The leftmost point of a line represents the single-element sub-array starting at that index, and each subsequent point extends the sub-array by one element to the right. The x-coordinate of a point is the index of the last element in the sub-array, and the y-coordinate is the sum of the sub-array. In this case, the original array from which sub-arrays are taken is [2, 3, -1, -20, 5, 10].]] In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. It can be solved in O(n) time and O(1) space. Formally, the task is to find indices i and j with 1 \\leq i \\leq j \\leq n , such that the sum \\sum_{x=i}^j A[x] is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention, the sum of all values of the empty subarray is zero.) Each number in the input array A could be positive, negative, or zero. For example, for the array of values [−2, 1, −3, 4, −1, 2, 1, −5, 4], the contiguous subarray with the largest sum is [4, −1, 2, 1], with sum 6. Some properties of this problem are: If the array contains all non-negative numbers, then the problem is trivial; a maximum subarray is the entire array. If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is permitted). Several different sub-arrays may have the same maximum sum. Although this problem can be solved using several different algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to shortest paths, a simple single-pass algorithm known as Kadane's algorithm solves it efficiently. ==Kadane's algorithm== ===No empty subarrays admitted=== Kadane's algorithm scans the given array A[1\\ldots n] from left to right. In the j th step, it computes the subarray with the largest sum ending at j ; this sum is maintained in variable current_sum . Moreover, it computes the subarray with the largest sum anywhere in A[1 \\ldots j] , maintained in variable best_sum , and easily obtained as the maximum of all values of current_sum seen so far, cf. line 7 of the algorithm. As a loop invariant, in the j th step, the old value of current_sum holds the maximum over all i \\in \\{ 1,\\ldots, j-1 \\} of the sum A[i]+\\cdots+A[j-1] . Therefore, current_sum +A[j] is the maximum over all i \\in \\{ 1,\\ldots, j-1 \\} of the sum A[i]+\\cdots+A[j] . To extend the latter maximum to also cover the case i=j , it is sufficient to also consider the singleton subarray A[j \\; \\ldots \\; j] . This is done in line 6 by assigning \\max(A[j], current_sum +A[j]) as the new value of current_sum , which after that holds the maximum over all i \\in \\{ 1, \\ldots, j \\} of the sum A[i]+\\cdots+A[j] . Thus, the problem can be solved with the following code, expressed in Python. def max_subarray(numbers): \"\"\"Find the largest sum of any contiguous subarray.\"\"\" best_sum = float('-inf') current_sum = 0 for x in numbers: current_sum = max(x, current_sum + x) best_sum = max(best_sum, current_sum) return best_sum If the input contains no positive element, the returned value is that of the largest element (i.e., the value closest to 0), or negative infinity if the input was empty. For correctness, an exception should be raised when the input array is empty, since an empty array has no maximum nonempty subarray. If the array is nonempty, its first element could be used in place of negative infinity, if needed to avoid mixing numeric and non-numeric values. The algorithm can be adapted to the case which allows empty subarrays or to keep track of the starting and ending indices of the maximum subarray. This algorithm calculates the maximum subarray ending at each position from the maximum subarray ending at the previous position, so it can be viewed as a case of dynamic programming. ===Empty subarrays admitted=== Kadane's algorithm, as originally published, is for solving the problem variant which allows empty subarrays. In such a variant, the answer is 0 when the input contains no positive elements (including when the input is empty). The variant is obtained with two changes in code: in line 3, best_sum should be initialized to 0 to account for the empty subarray A[0 \\ldots -1] best_sum = 0; and line 6 in the for loop current_sum should be updated to max(0, current_sum + x) .{{NoteTag |While does not mention this difference, using x instead of 0 in the above version without empty subarrays achieves maintaining its loop invariant current_sum =\\max_{i \\in \\{ 1, ..., j-1 \\}} A[i]+...+A[j-1] at the beginning of the j th step. }} current_sum = max(0, current_sum + x) As a loop invariant, in the j th step, the old value of current_sum holds the maximum over all i \\in \\{ 1,\\ldots, j \\} of the sum A[i]+\\cdots+A[j-1] . Therefore, current_sum +A[j] is the maximum over all i \\in \\{ 1,\\ldots, j \\} of the sum A[i]+\\cdots+A[j] . To extend the latter maximum to also cover the case i=j+1 , it is sufficient to also consider the empty subarray A[j+1 \\; \\ldots \\; j] . This is done in line 6 by assigning \\max(0, current_sum +A[j]) as the new value of current_sum , which after that holds the maximum over all i \\in \\{ 1, \\ldots, j+1 \\} of the sum A[i]+\\cdots+A[j] . Machine-verified C / Frama-C code of both variants can be found here. ===Computing the best subarray's position=== The algorithm can be modified to keep track of the starting and ending indices of the maximum subarray as well. 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. ===Complexity=== The runtime complexity of Kadane's algorithm is O(n) and its space complexity is O(1) . ==Notes== ==Notes== ==References== . . .",
  "categories": [
    "23118434",
    "23603337",
    "23617828",
    "25257581",
    "26709286",
    "62317677"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1365852288",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1784918333.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001365852288",
    "type": "webpage",
    "title": "Maximum subarray problem",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/maximum-subarray-problem",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          11
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          11
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001365852288",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1365852288",
    "note": "Immutable snapshot enwiki-001365852288"
  }
}