import java.util.Arrays;
import java.util.Random;

public class MaxContiguousSubsequenceSum {

  public static int compute1(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 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;
    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[] generateRandomArray(Random rand, int n, int k) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = rand.nextInt(k);
      if (rand.nextBoolean()) { arr[i] = -arr[i]; }
    }
    return arr;
  }
  
  public static void main(String[] args) {
    Random rand = new Random();
    int size = 10;
    int range = 10;
    System.out.print(String.format("Generating a random array of size %d... ", size));
    int[] arr = generateRandomArray(rand, size, range);
    System.out.println("complete!");
    System.out.println(String.format("arr = %s", Arrays.toString(arr)));
    System.out.println(String.format("compute1(arr) = %d", compute1(arr)));
    System.out.println(String.format("compute2(arr) = %d", compute2(arr)));
    System.out.println(String.format("compute3(arr) = %d", compute3(arr)));
  }
}