Maximum Subarray Problem -- Classic Algorithms in Matlab

2 次查看（过去 30 天）

显示更早的评论

Matlab2010 2014-3-13

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/121409-maximum-subarray-problem-classic-algorithms-in-matlab

评论： Salaheddin Hosseinzadeh 2014-3-13

Trying to implement some forms of this classic algorithm

http://www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/L02.pdf

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Not quite there; anyone fancy having a look at the O(n log n) and O(n) attempts -- working from the PDF above.

function MaxSubArrayProblem()
clc;
A = randn(100,1);
tic;
B1=MaxSubArray_BruteForce(A); %O(n^3)
t1=toc;
tic;
B2=MaxSubArray_reUseData(A); %O(n^2)
t2=toc;
tic;
B3=MaxSubArray_divideAndConquer(A); %O(n log n)
t3=toc;
tic;
B4=MaxSubArray_revisualizing(A); %O(n)
t4=toc;
isequaln(B1,B2,B3,B4)
bar([t1 t2 t3 t4]);
end
function B= MaxSubArray_BruteForce(A)
B= NaN(length(A),3);
VMAX = -inf;
for i = 1 : length(A)
    for j = i: length(A)
        V = sum(A(i:j));
        if(V>VMAX)
            VMAX = V;
            from = i;
            to = j;
        end
    end   
    disp(['Largest Sum: ' num2str(VMAX) ' from ' num2str(from) ' to ' num2str(to)]); 
    B(i,:) = [VMAX from to];
end
end
function B= MaxSubArray_reUseData(A)
B= NaN(length(A),3);
VMAX = -inf;
for i = 1 : length(A)
    V = 0;
    for j = i: length(A)
        V = V + A(j);
        if(V>VMAX)
            VMAX = V;
            from = i;
            to = j;
        end
    end   
    disp(['Largest Sum: ' num2str(VMAX) ' from ' num2str(from) ' to ' num2str(to)]);  
    B(i,:) = [VMAX from to];
end
end
function B= MaxSubArray_divideAndConquer(A)
B= NaN(length(A),3);
for i = 1: length(A)
    for j = 1: length(A)
        myMax = MCS(A,i,j);
    end
    B(i,:) = [myMax i j];
end
end
function myMax = MCS(A,i,j)
if(i==j)
    myMax = A(i:j);
else
    myMax1 = MCS(A,i,floor(0.5*(i+j)));
    myMax2 = MCS(A,floor(0.5*(i+j))+1,j);
    myMax3 = MCS(A,i,j);
      myMax = max([myMax1 myMax2 myMax3]);
  end
end
function B= MaxSubArray_revisualizing(A)
B= NaN(length(A),3);
VMAX = -inf;
from = 1;
T = A(1);
V = A(1);
Tmin = min(0,T);
for j = 2: length(A)
    T = T + A(j);
    if((T-Tmin)>V)
        V = T - Tmin;
        %
        VMAX = V;
        to = j;
    end
    if(T<Tmin)
        Tmin = T;
        from = j;
    end
    disp(['Largest Sum: ' num2str(VMAX) ' from ' num2str(from) ' to ' num2str(to)]);  
    B(j,:) = [VMAX from to];
end   
end