Day 4 - Challenge 2 - Largest Subarray Sum

Solving the Largest Subarray Sum Problem

Introduction

Algorithmic problem-solving often takes us through a labyrinth of data manipulation and innovative algorithm design. In this blog post, we will explore the intriguing "Largest Subarray Sum" problem. We will delve into the problem's significance and intricacies, and present a JavaScript solution that not only conquers the challenge but also illuminates fundamental algorithmic techniques.

Understanding the Problem

Consider an array of integers, e.g., [1, -3, 2, 1, -1]. The task is to find the contiguous subarray (a subset of the array with consecutive elements) that yields the largest sum. In this example, the subarray [2, 1] has the largest sum of 3. The objective is to devise an algorithm that not only identifies the maximum sum but also provides the starting and ending indices of the subarray.

Approach: Kadane's Algorithm

Kadane's Algorithm, named after computer scientist Jay Kadane, is a widely used approach to solving the Largest Subarray Sum problem. This algorithm employs two variables: currentMax and globalMax. The currentMax variable keeps track of the maximum sum subarray ending at the current index, while globalMax tracks the maximum sum found overall. The algorithm iterates through the array, evaluating each element's contribution to the current subarray.

JavaScript Implementation

Let's delve into the JavaScript implementation of Kadane's Algorithm for the Largest Subarray Sum problem:

function findLargestSubarraySum(arr) {
    let currentMax = arr[0];
    let globalMax = arr[0];
    let startIndex = 0;
    let endIndex = 0;
    let tempStartIndex = 0;

    for (let i = 1; i < arr.length; i++) {
        if (currentMax + arr[i] < arr[i]) {
            currentMax = arr[i];
            tempStartIndex = i;
        } else {
            currentMax = currentMax + arr[i];
        }

        if (currentMax > globalMax) {
            globalMax = currentMax;
            startIndex = tempStartIndex;
            endIndex = i;
        }
    }

    return {
        maxSum: globalMax,
        subarray: arr.slice(startIndex, endIndex + 1),
        startIndex: startIndex,
        endIndex: endIndex
    };
}

// Example usage
const inputArray = [1, -3, 2, 1, -1];
const result = findLargestSubarraySum(inputArray);

console.log("Maximum Sum:", result.maxSum);
console.log("Subarray:", result.subarray);
console.log("Starting Index:", result.startIndex);
console.log("Ending Index:", result.endIndex);

Explanation of the Program

1. Function Definition: We define a function findLargestSubarraySum that takes an array arr as input.

2. Initialization: Initialize currentMax and globalMax with the first element of the array. Also, initialize startIndex, endIndex, and tempStartIndex to keep track of indices.

3. Iterating through the Array: Starting from the second element, iterate through the array.

4. Updating currentMax: At each step, we decide whether it's better to start a new subarray from the current element or extend the existing subarray. If extending the subarray results in a smaller sum than the current element itself, we start a new subarray from that element.

5. Updating globalMax: After updating currentMax, we compare it with globalMax. If currentMax is larger, we update globalMax and also update startIndex and endIndex to the values of tempStartIndex and the current index.

6. Returning the Result: After iterating through the entire array, the function returns an object containing the maxSum, the subarray with the largest sum, and the startIndex and endIndex of that subarray.

7. Example Usage: An example array is provided, and the function is called to find the largest subarray sum and associated information. The results are then printed to the console.

    

Demo

Enter an array of integers (comma-separated):

Maximum Subarray Sum:

Subarray:

Starting Index:

Ending Index:

Conclusion

The "Largest Subarray Sum" problem is not only a captivating algorithmic challenge but also a testament to the power of innovative thinking in problem-solving. By diving into the details of Kadane's Algorithm and its JavaScript implementation, we gain insights into core algorithmic concepts. This knowledge empowers us to tackle complex computational hurdles and uncover elegant solutions to a variety of real-world problems.

Now write the same program in your favorite language in comment section. 

Other Challenges:

1. Day 2 Challenges
2. Day 3 Challenges
3. Day 4 Challenges