Problem: Iterative Counting

In this problem, we’ll look at some loop-based code written in Java to compute the maximum contiguous subsequence sum of an input array. This quantity is the largest sum obtained by adding together a subsequence of elements in the array. For example, in the array:

int[] example = { 3, 4, -8, 2, 1, -2, 8, 5, -20, 10 };

// max contiguous subsequence sum =
//   2 + 1 - 2 + 8 + 5 = 14

The maximum contiguous subsequence sum is 14 obtained from summing the subsequence 2, 1, -2, 8, 5. This problem is interesting because our algorithm needs to detect that even though -2 breaks up the summation, it is more “profitable” to keep -2 because the sum of its previous values—2, 1—is greater.

Below, you will find three implementations of algorithms that solve this problem. For this problem, you don’t need to know how they work precisely, but you might find it interesting to work through the code on your own to understand each approach.

class Main {
  public static int compute1(int[] arr) {
    int max = 0;
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
      sum = Math.max(0, arr[i] + sum);
      max = Math.max(sum, max);
    }
    return max;
  }

  public static int compute2(int[] arr) {
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
      int sum = 0;
      for (int j = i; j < arr.length; j++) {
        sum += arr[j];
        max = Math.max(max, sum);
      }
    }
    return max;
  }

  public static int compute3(int[] arr) {
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
      for (int j = i; j < arr.length; j++) {
        int sum = 0;
        for (int k = i; k <= j; k++) {
          sum += arr[k];
        }
        max = Math.max(max, sum);
      }
    }
    return max;
  }

  public static void main(String args[]) {
    int[] example = { 3, 4, -8, 2, 1, -2, 8, 5, -20, 10 };
    System.out.println(compute1(example));
    System.out.println(compute2(example));
    System.out.println(compute3(example));
  }
}

If you would like to play around with this code, you can copy-paste it directly into the Repl.it Java 10 Online Interpreter and run it.

1. First, identify a relevant critical operation to count among the various compute functions. Recall that this operation should be one that is characteristic of the behavior of the functions in question. When loops are involved, you should consider choosing an operation that occurs in the innermost loop because that operation will be run with the most frequency.

2. Write down combinatorial descriptions using summation notation for the number of critical operation each function performs as a function of the length of their input arrays, call that value \(n\). Be mindful of using appropriate bounds on your summations.

3. Use summation identities to simplify the descriptions of compute1 and compute2 so that they do not contain summations. You will find the following identities useful:

   \[\begin{gather} \sum_{i=1}^{n} c = cn \\ \sum_{i=1}^{n} f(i) + g(i) = \sum_{i=1}^{n} f(i) + \sum_{i=1}^{n} g(i) \\ \sum_{i=1}^{n} i = 1 + \cdots + n = \frac{n(n+1)}{2} \end{gather}\]

   As a challenge, you may also consider trying to simplify the third description as well!