-- Function Max_Subsequence_Sum is the O(N log N) algorithm in Figure 2.7 -- A short test program is provided -- Max3 is implemented; it returns the maximum of three integers with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Fig2_7 is type Input_Array is array( Integer range <> ) of Integer; An_Array : Input_Array( 1..8 ) := ( 4, -3, 5, -2, -1, 2, 6, -2 ); -- Return the maximum of A, B, and C function Max3( A, B, C: Integer ) return Integer is begin if A > B then if A > C then return A; else return C; end if; else if B > C then return B; else return C; end if; end if; end Max3; function Max_Subsequence_Sum( A: Input_Array ) return Integer is Max_Left_Sum, Max_Left_Border_Sum : Integer := 0; Max_Right_Sum, Max_Right_Border_Sum : Integer := 0; Left_Border_Sum, Right_Border_Sum : Integer := 0; Center : Integer := ( A'First + A'Last ) / 2; begin if A'Length = 1 then -- Base case if A( A'First ) > 0 then return A( A'First ); else return 0; end if; end if; -- Compute the maximum for each of the two halves recursively Max_Left_Sum := Max_Subsequence_Sum( A( A'First..Center ) ); Max_Right_Sum := Max_Subsequence_Sum( A( Center+1..A'Last ) ); -- Compute the maximum sum of the sequence that includes -- the last element in the first half for I in reverse A'First..Center loop Left_Border_Sum := Left_Border_Sum + A( I ); if Left_Border_Sum > Max_Left_Border_Sum then Max_Left_Border_Sum := Left_Border_Sum; end if; end loop; -- Compute the maximum sum of the sequence that includes -- the first element in the second half for I in Center+1..A'Last loop Right_Border_Sum := Right_Border_Sum + A( I ); if Right_Border_Sum > Max_Right_Border_Sum then Max_Right_Border_Sum := Right_Border_Sum; end if; end loop; -- Return the maximum of the three possibilities return Max3( Max_Left_Sum, Max_Right_Sum, Max_Left_Border_Sum + Max_Right_Border_Sum ); end Max_Subsequence_Sum; begin Put( Max_Subsequence_Sum( An_Array ) ); New_Line; end Fig2_7;