%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Largest Sum Sub-Array
% written by Nathan Feaver, 7/25/11
%
% This program generates an array of randomly generated integers(positive
% and negative) and then finds the sub-array with the maximum sum.
%
% I solved this problem by trying to imitate the way that my brain found
% the largest sum. When I looked at an array of random numbers, I started
% by finding areas that had a lot of high positive numbers and set the
% boundaries by finding areas that started to be particularly negative.
%
% To program this process, I first combined all neighboring same sign
% (positive or negative) numbers and kept track of the running sum in a new array, where
% newArray(i) = neighboring_positive_element_sum + newArray(i-1); or
% newArray(i) = neighboring_negative_element_sum + newArray(i-1); so that
% regions of the array that are positive increase the values in newArray
% while regions that are negative decrease the values.
%
% Once newArray was assembled, I found the largest span from a local
% minimum to a local maximim in newArray. This corresponds to the largest
% sum sub-array. The largest span can be
%
% I compare my solution and the brute force solution (summing every
% possible sub-array) to Kadane's algorithm (most-efficient
% linear time solution).
%
% My solution is more efficient than brute force method for
% arrays larger than 400 elements since it is O(n) compared to
% O((n^2+n)/2) but has a more involved process so it is less efficient for
% smaller arrays.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - Initialization ----------------------------------------------
clear;
clc;
close all;
defaultInput = 1; % 1 -> defaults on, no user input
defSize = 1000;
% - User Input --------------------------------------------------
% Number of values in array
if defaultInput ~= 1
arrsize = input('How many values would you like the array to hold? \n');
if isempty(arrsize)
arrsize = defSize;
end
else
arrsize = defSize;
end
% - Program/Performance variables -------------------------------
maxval = 15; % Maximum value of values in array
array = round(2*maxval*(rand(arrsize,1)-0.5)); % Hypothetical array that is given in problem statement
rpt = 1; % Number of times to repeat calculation to average out small variations in calculation speeds
t = zeros(rpt,1); % cpu time required for each calculation
tk = zeros(rpt,1); % cpu time required for each calculation
tb = zeros(rpt,1); % same as above but for brute force calculations
% - User Input --------------------------------------------------
if defaultInput ~= 1
reply = input('\nWould you like to see the starting array [y/n]?\n', 's');
if isempty(reply)
reply = 'n';
end
if reply == 'y' || reply == 'Y'
fprintf('\nArray: \n[')
fprintf('%i, ',array(1:arrsize-1,1));
fprintf('%i]\n',array(arrsize,1));
end
end
% - Body --------------------------------------------------------
for z = 1:rpt
% - Feaver's Method ---------------------------------------------
%tic
% First combine all positive/negative regions and record running summation
%nArrsize = ceil(0.8*arrsize)+1;
%newArray = zeros(arrsize+1, 1); % newArray stores combined positive/negative values // Columns: value, Index_of_Start, Index_of_End
sum = 0;
% Now find largest span in running summation to find sub-array soultion
min = 0; % Keep track of minimum - left side of largest span
minLoc = 0; % Location of minimum in matrix - for backtracking start point of sub-array
currentSpan = 0; % sum of current sub-array
maxSpan = 0; % sum of largest sub-array found
st=zeros(arrsize,4);
for i = 1:arrsize
sum = sum + array(i);
tic
if sum < min % Find minimum
min = sum;
minLoc = i;
end
st(i,1) = toc;
tic
currentSpan = sum - min;
if currentSpan > maxSpan % Keep track of sub-array sum and indices
maxSpan = currentSpan;
leftInd = minLoc+1;
rightInd = i;
end
st(i,2) = toc;
end
%{
for i = 2:count
if newArray(i) < min % Find minimum
min = newArray(i,1);
minLoc = i;
end
currentSpan = newArray(i,1) - min;
if currentSpan > maxSpan % Keep track of sub-array sum and indices
maxSpan = currentSpan;
leftInd = newArray(minLoc+1,2);
rightInd = newArray(i,3);
end
end
%}
%t(z) = toc; % End of program, check running time for performance
% - Kadane's Method ---------------------------------------------
%tic % start clock
left = 1;
right = 1;
newMaxsum = 0;
maxsum = 0;
newLeft = 1;
for newRight = 1:arrsize % cycle placeholder value through entire array
newMaxsum = newMaxsum + array(newRight); % calculate current sum
tic
if newMaxsum > maxsum % record if sum is a new maximum
maxsum = newMaxsum;
right = newRight;
left = newLeft;
end
st(newRight,3) = toc;
tic
if newMaxsum < 0 % Removes negative regions from summation
newMaxsum = 0;
newLeft = newRight+1;
end
st(newRight,4) = toc;
end
%tk(z) = toc; % End of program, check running time for performance
% - Brute Force Method - Check all possible sub-arrays ----------
tic % start clock
leftb = 1;
rightb = 1;
maxsumb = 0;
for j = 1:arrsize % Cycle through all sub-array starting indices
newMaxsum = 0;
for i = j:arrsize % Cycle through all sub-array ending indices
newMaxsum = newMaxsum + array(i,1); % calculate current sum
if newMaxsum>maxsumb % record if sum is a new maximum
maxsumb = newMaxsum;
leftb = j;
rightb = i;
end
end
end
tb(z) = toc; % End of program, check running time for performance
end
% - Program Output ----------------------------------------------
if left == leftb && left == leftInd && right == rightb && right == rightInd
fprintf('\nThe same solution was reached by all methods.\n');
end
%fprintf('Kadane''s algorithm was %.0f times faster than Nathan''s algorithm.\n', mean(t)/mean(tk));
%fprintf('Nathan''s algorithm was %.1f times faster than brute force.\n', mean(tb)/mean(t));
fprintf('\nThe sub-array with the highest sum is found from indice %.0d\nto indice %.0d and has a sum of %.0d \n', leftInd, rightInd, maxSpan);
if defaultInput ~= 1
reply = input('\nWould you like to display the maximum sub-array [y/n]?\n', 's');
if isempty(reply)
reply = 'n';
end
if reply == 'y' || reply == 'Y'
fprintf('\nArray: \n[')
fprintf('%i, ',array(left:right-1,1));
fprintf('%i]\n',array(right,1));
end
end