1.4.3 Maximum Subarray Sum (Kadane)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

/*

Given an array of numbers, determine the maximum possible sum of any contiguous subarray. Kadane's
algorithm scans through the array, at each index computing the maximum nonnegative sum subarray
ending there. Either this subarray is empty (in which case its sum is zero), or it consists of one
more element than the maximum sequence ending at the previous position. This can be adapted to
compute the maximal submatrix sum as well.

- `max_subarray_sum(lo, hi, &res_lo, &res_hi)` returns the maximal subarray sum for the range
  [`lo`, `hi`), where `lo` and `hi` are random-access iterators to numeric types. This
  implementation requires operators `+` and `<` to be defined on the iterators' value type.
  Optionally, two `int` pointers may be passed to store the inclusive boundary indices
  [`res_lo`, `res_hi`] of the resulting subarray. By convention, the empty subarray is allowed, so
  an input range consisting of only negative values returns 0 with an empty result interval.
- `max_submatrix_sum(a, &r1, &c1, &r2, &c2)` returns the largest sum of any rectangular submatrix
  for a matrix `a` with $m$ rows and $n$ columns. This implementation requires operators `+` and `<`
  to be defined on the iterators' value type. Optionally, four `int` pointers may be passed to store
  the boundary indices of the resulting subarray, with (`r1`, `c1`) specifiying the top-left index
  and (`r2`, `c2`) specifying the bottom-right index. By convention, the empty submatrix is allowed,
  so an input matrix consisting of only negative values returns 0 with an empty result interval.

Time Complexity:
- O(n) per call to `max_subarray_sum()`, where $n$ is the distance between `lo` and `hi`.
- O(m*n^2) per call to `max_submatrix_sum()`, where $m$ is the number of rows and $n$ is the number
  of columns in the matrix.

Space Complexity:
- O(1) auxiliary for `max_subarray_sum()`.
- O(m) auxiliary heap space for `max_submatrix_sum()`, where $m$ is the number of rows in the
  matrix.

*/

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <vector>

template<class It>
auto max_subarray_sum(It lo, It hi, int *res_lo = nullptr, int *res_hi = nullptr) {
  using T = typename std::iterator_traits<It>::value_type;
  if (lo == hi) {
    return T();
  }
  int curr_begin = 0, begin = 0, end = -1;
  T sum = 0, max_sum = 0;
  for (It it = lo; it != hi; ++it) {
    sum += *it;
    if (sum < 0) {
      sum = 0;
      curr_begin = (it - lo) + 1;
    } else if (max_sum < sum) {
      max_sum = sum;
      begin = curr_begin;
      end = it - lo;
    }
  }
  if (res_lo != nullptr && res_hi != nullptr) {
    *res_lo = begin;
    *res_hi = end;
  }
  return max_sum;
}

template<class T>
T max_submatrix_sum(
    const std::vector<std::vector<T>> &a, int *r1 = nullptr, int *c1 = nullptr, int *r2 = nullptr,
    int *c2 = nullptr
) {
  if (a.empty() || a[0].empty()) {
    return T();
  }
  int rows = static_cast<int>(a.size()), cols = static_cast<int>(a[0].size());
  T sum, max_sum = 0;
  for (int clo = 0; clo < cols; clo++) {
    std::vector<T> sums(rows, 0);
    for (int chi = clo; chi < cols; chi++) {
      for (int i = 0; i < rows; i++) {
        sums[i] += a[i][chi];
      }
      int rlo, rhi;
      sum = max_subarray_sum(sums.begin(), sums.end(), &rlo, &rhi);
      if (max_sum < sum) {
        max_sum = sum;
        if (r1 != nullptr && c1 != nullptr && r2 != nullptr && c2 != nullptr) {
          *r1 = rlo;
          *c1 = clo;
          *r2 = rhi;
          *c2 = chi;
        }
      }
    }
  }
  return max_sum;
}

/*** Example Usage and Output:

Maximal sum subarray:
4 -1 2 1

Maximal sum submatrix:
9 2
-4 1
-1 8

***/

#include <cassert>
#include <iostream>
using namespace std;

int main() {
  {
    vector<int> a{-2, -1, -3, 4, -1, 2, 1, -5, 4};
    int lo = 0, hi = 0;
    assert(max_subarray_sum(a.begin(), a.begin() + 3) == 0);
    assert(max_subarray_sum(a.begin(), a.end(), &lo, &hi) == 6);
    cout << "Maximal sum subarray:" << endl;
    for (int i = lo; i <= hi; i++) {
      cout << a[i] << " ";
    }
    cout << endl;
  }
  {
    // clang-format off
    vector<vector<int>> a{{0, -2, -7, 0, 5},
                          {9, 2, -6, 2, -4},
                          {-4, 1, -4, 1, 0},
                          {-1, 8, 0, -2, 3}};
    // clang-format on
    int r1 = 0, c1 = 0, r2 = 0, c2 = 0;
    assert(max_submatrix_sum(a, &r1, &c1, &r2, &c2) == 15);
    cout << "\nMaximal sum submatrix:" << endl;
    for (int i = r1; i <= r2; i++) {
      for (int j = c1; j <= c2; j++) {
        cout << a[i][j] << " ";
      }
      cout << endl;
    }
  }
  return 0;
}