MaxSliceSum

Find a maximum sum of a compact subsequence of array elements
ℹ️ © Codility, 2009-2018

Problem

A non-empty array A consisting of n integers is given. A pair of integers (p, q), such that 0 ≤ p ≤ q < n, is called a slice of array A. The sum of a slice (p, q) is the total of A[p] + A[p + 1] + … + A[q].

Write a function that, given an array A consisting of n integers, returns the maximum sum of any slice of A.

For example, given array A such that: A[0] = 3, A[1] = 2, A[2] = -6, A[3] = 4, A[4] = 0, the function should return 5 because:
• (3, 4) is a slice of A that has sum 4;
• (2, 2) is a slice of A that has sum −6;
• (0, 1) is a slice of A that has sum 5,
• no other slice of A has sum greater than (0, 1).

Assume that:
• n is an integer within the range [1 … 1,000,000];
• each element of array A is an integer within the range [-1,000,000 … 1,000,000];
• the result will be an integer within the range [-2,147,483,648 … 2,147,483,647].

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(n), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Solution

C#

using System;
class Solution {
  public int solution(int[] A) {
    int r = A[0];
    int t = A[0];
    int n = A.Length;
    for (int i = 1; i < n; i++) {
      t = Math.Max(A[i], t + A[i]);
      r = Math.Max(r, t);
    }
    return r;
  }
}

Java

import java.lang.Math;
class Solution {
  public int solution(int[] A) {
    int r = A[0];
    int t = A[0];
    int n = A.length;
    for (int i = 1; i < n; i++) {
      t = Math.max(A[i], t + A[i]);
      r = Math.max(r, t);
    }
    return r;
  }
}

JavaScript

function solution(A) {
  let r = A[0];
  let t = A[0];
  let n = A.length;
  for (let i = 1; i < n; i++) {
    t = Math.max(A[i], t + A[i]);
    r = Math.max(r, t);
  }
  return r;
}

PHP

function solution($A) {
  $r = $A[0];
  $t = $A[0];
  $n = count($A);
  for ($i = 1; $i < $n; $i++) {
    $t = max($A[$i], $t + $A[$i]);
    $r = max($r, $t);
  }
  return $r;
}