Let A be an array of integers (positive or negative). Assume that the array is of size n. The subarray A[i..j] is the part of the array that starts at index i and ends at index j, where 0 i j n-1. Let s_ij equal the sum of the integers in A[i..j].

We wish to solve the following problem:

Find the maximum value for s_ij over all subarrays with maximum leght of 3 in array A, where 0 i j n-1.

The three algorithms given below solve this problem. NOTE: If all of the values in the array are negative, then the maximum value for s_ij is 0 by default.

Example: If the array contains the values { -1, 12, -3, 14, -4, 3 }, then the maximum sum over all subarrays is 23 (for the subarray {12, -3, 14}). If the array contains the values { 2, -3, 5, -1, 7}, then the maximum sum over all subarrays is 11 (for the subarray {5, -1, 7}).

ALGORITHM 1

Start with a maximum sum of 0. Compute the sum of each 1-element subarray, then compute the sum of each 2-element subarray, then compute the sum of each 3-element subarray, etc. For each sum you compute, if it is larger than the maximum sum youve seen, then it becomes the maximum sum.