K-Concatenation Maximum Sum LeetCode solution in C++

1
class Solution {
2
 public:
3
  // Compute max score across all cases
4
  //  1. (arr_sum * k) [array sum is positive]
5
  //  2. (subarray_sum) [k == 1]
6
  //  3. if k > 1:
7
  //          if k == 2: lm + rm
8
  //          else: lm + (arr_sum * (k-2)) + rm
9

10
  // For case:3, instead of running over the entire modified array,
11
  //  we can just add (arr_sum * (k-2)) to the 's' instead.
12

13
  int kConcatenationMaxSum(vector<int> &arr, int k) {
14
    const int n = arr.size();
15
    int64_t s{}, min_s{}, max_score{INT_MIN};
16

17
    // This loop computes the answer for case:2
18
    for (int i = 0; i < n; i++) {
19
      s += arr[i];
20
      max_score = max(max_score, s - min_s);
21
      min_s = min(min_s, s);
22
    }
23

24
    if (k > 1) {
25
      // Condition for case:3 part:2
26
      // At this point, 's' holds the sum of all numbers in 'arr'
27
      if (k > 2) s = max(s, s + s * (k - 2));
28
      // Base logic for case:3 part:1
29
      for (int i = 0; i < n; i++) {
30
        s += arr[i];
31
        max_score = max(max_score, s - min_s);
32
        min_s = min(min_s, s);
33
      }
34
    }
35

36
    // If all numbers are positive, case:1 is automatically computed with
37
    //  the method given above.
38
    //  Because (for an array with all positive elements):
39
    //      (max_score [after first loop]) == (arr_sum)
40
    //      s is updated to (s + s * (k - 2))
41
    //      Finally, s (and subsequently max_score) is also updated to (arr_sum
42
    //      * k)
43

44
    // Apply modulo on answer and convert to int
45
    int ans = static_cast<int>(max_score % (1000000000 + 7));
46
    // Subarray can have length == 0 (and sum == 0)
47
    if (ans < 0)
48
      return 0;
49
    else
50
      return ans;
51
  }
52
};