Question

How to find the maximum length of a subarray having a sum equal to K in Pascal

Answer 1

program MaxLengthSubarrayEqualsToK;

uses crt;

const
  N = 8; // Size of the array
  MAX_MAP_SIZE = 1024; // Arbitrary size for map simulation

type
  TMap = record
    keys: array[1..MAX_MAP_SIZE] of integer;
    values: array[1..MAX_MAP_SIZE] of integer;
    count: integer;
  end;

// Initialize map
procedure InitMap(var map: TMap);
begin
  map.count := 0;
end;

// Check if key exists in map
function MapHas(var map: TMap; key: integer): boolean;
var
  i: integer;
begin
  for i := 1 to map.count do
    if map.keys[i] = key then
    begin
      MapHas := true;
      exit;
    end;
  MapHas := false;
end;

// Get value by key
function MapGet(var map: TMap; key: integer): integer;
var
  i: integer;
begin
  for i := 1 to map.count do
    if map.keys[i] = key then
    begin
      MapGet := map.values[i];
      exit;
    end;
  MapGet := -1; // Default if not found
end;

// Set key-value pair if key not already present
procedure MapSet(var map: TMap; key, value: integer);
begin
  if not MapHas(map, key) then
  begin
    inc(map.count);
    map.keys[map.count] := key;
    map.values[map.count] := value;
  end;
end;

// Function to find the maximum length of subarray with sum equal to K
function MaxLengthSubarrayEqualsToK(arr: array of integer; K: integer): integer;
var
  map: TMap;
  maxLength, cumulativeSum, i: integer;
begin
  InitMap(map); // To store cumulative sum and its index
  maxLength := 0;
  cumulativeSum := 0;

  for i := 0 to High(arr) do
  begin
    cumulativeSum := cumulativeSum + arr[i];

    // If the cumulative sum equals K, update maxLength
    if cumulativeSum = K then
      maxLength := i + 1;

    // If (cumulativeSum - K) exists in the map, update maxLength
    if MapHas(map, cumulativeSum - K) then
      if (i - MapGet(map, cumulativeSum - K)) > maxLength then
        maxLength := i - MapGet(map, cumulativeSum - K);

    // Store the cumulative sum in the map if not already present
    MapSet(map, cumulativeSum, i);
  end;

  MaxLengthSubarrayEqualsToK := maxLength;
end;

var
  arr: array[0..N-1] of integer = (1, -1, 5, -2, -3, 2, 3, 3);
  K: integer;
  result: integer;

begin
  clrscr;
  K := 3;

  // 1, -1, 5, -2 = 3 (length 4)
  // 5, -2 = 3 (length 2)
  // -2, -3, 2, 3, 3 = 3 (length 5)

  result := MaxLengthSubarrayEqualsToK(arr, K);
  writeln(result); 
end.



(*
run:

5

*)

 

70+ SQL courses for beginners and professionals