Kadane’s Algorithm & Prefix Sum

KADANE’S ALGORITHM

The Kadane’s algorithm is a well-known algorithm for finding the maximum subarray sum in a given array of integers in a contiguous subarray.

Working:-

The algorithm works by maintaining two variables:

· one to keep track of the maximum subarray sum ending at the current position

· another to keep track of the maximum subarray sum seen so far.

· It iterates through the array, updating these variables at each step.

· The key insight is that the maximum subarray sum ending at the current position is either the sum of the previous subarray ending at that position plus the current element, or just the current element itself.

Outline of the Kadane’s algorithm:-

1.Initialize two variables, maxEndingHere and maxSoFar, to the first element of the array.

2.Iterate through the array from the second element to the end.

3.For each element, update maxEndingHere to be the maximum of the current element and the sum of maxEndingHere and the current element.

4.Update maxSoFar to be the maximum of maxSoFar and maxEndingHere.

5.After iterating through the entire array, the value of maxSoFar represents the maximum subarray sum.

The time complexity of Kadane’s algorithm is O(n).

public class KadanesAlgorithm {
    public static int maxSubArraySum(int[] arr) {
        // Check if the array is empty
        if (arr == null || arr.length == 0) {
            return 0;
        }

        // Initialize variables to keep track of the maximum subarray sum ending at the current position (maxEndingHere)
        // and the maximum subarray sum seen so far (maxSoFar)
        int maxEndingHere = arr[0];
        int maxSoFar = arr[0];

        // Iterate through the array from the second element to the end
        for (int i = 1; i < arr.length; i++) {
            // Update maxEndingHere to be the maximum of the current element and the sum of maxEndingHere and the current element
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);

            // Update maxSoFar to be the maximum of maxSoFar and maxEndingHere
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        // After iterating through the entire array, maxSoFar represents the maximum subarray sum
        return maxSoFar;
    }

    public static void main(String[] args) {
        // Example array
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int result = maxSubArraySum(arr);
        System.out.println("Maximum subarray sum: " + result);
    }
}

Here are some problem statements where Kadane’s algorithm is commonly applicable:-

1. Maximum Subarray Sum: Given an array of integers, find the contiguous subarray with the largest sum.
2. Largest Sum Increasing Subsequence: Find the sum of the maximum sum increasing subsequence in an array.
3. Stock Buy and Sell: Given an array representing stock prices on different days, find the maximum profit that can be earned by buying and selling.
4. Circular Subarray Sum: Given a circular array, find the maximum subarray sum allowed to wrap around to the beginning of the array.
5. Maximum Product Subarray: Find the contiguous subarray with the largest product in an array of integers.
6. Longest Increasing Subarray: Find the length of the longest increasing subarray.

PREFIX SUM

a prefix sum is an array derived from the input array, where the value at each index represents the sum of all the elements in the original array up to that index, also known as the cumulative sum array.

Example:-

Suppose you have an array arr = [1, 2, 3, 4, 5].

prefixSum[0] = 1

prefixSum[1] = 1 + 2 = 3

prefixSum[2] = 1 + 2 + 3 = 6

prefixSum[3] = 1 + 2 + 3 + 4 = 10

prefixSum[4] = 1 + 2 + 3 + 4 + 5 = 15

So, the prefix sum array for arr is [1, 3, 6, 10, 15].

public class PrefixSumExample {

    public static int[] calculatePrefixSum(int[] arr) {

        int n = arr.length;
        int[] prefixSum = new int[n];
        prefixSum[0] = arr[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        return prefixSum;
    }

    public static void main(String[] args) {
        
        int[] arr = {1, 2, 3, 4, 5};
        int[] result = calculatePrefixSum(arr);

        // Print the original array and the prefix sum array
        System.out.print("Original Array: [");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(", ");
            }
        }

        System.out.print("Prefix Sum Array: ");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) {
                System.out.print(", ");
            }
        }
    }
}

Here are some problem statements where Prefix sum is commonly applicable:-

1. Range Sum Queries:

· Problem: Given an array, perform multiple queries to find the sum of elements in a specific range [i, j].

· Solution: The range sum can be obtained as prefixSum[j] — prefixSum[i-1] (assume i > 0).

2. Subarray Sum Equals K:

· Problem: Given an array of integers, find the total number of continuous subarrays whose sum equals a specific value k.

· Solution: Use the prefix sum array to calculate the cumulative sum at each index. The number of subarrays with a sum equal to k can be determined by storing the count of each prefix sum and updating it as you iterate through the array.

3. Cumulative Frequency:

· Problem: Given an array of frequencies, find the cumulative frequency at each index.

. Solution: The prefix sum array can be used to calculate cumulative frequencies efficiently.

4. Count Triplets with Sum Smaller than a Given Value:

· Problem: Given an array of integers, count the number of triplets with a sum smaller than a given value.

· Solution: Sort the array and use the prefix sum array to efficiently count triplets.