. Day 4 - Challenge 2 - Largest Subarray Sum Skip to main content

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

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

 

Labels:

Comments

Post a Comment

Popular posts from this blog

Day 9 - Challenge 1 - Product of Array Except Self

Solving the "Product of Array Except Self" Problem in JavaScript Are you ready to dive into a common coding challenge that not only tests your programming skills but also sharpens your problem-solving mindset? If you're up for the challenge, let's tackle the "Product of Array Except Self" problem together using JavaScript. This problem requires us to return an array where each element at index i is the product of all the elements in the original array except the one at index i . Understanding the Problem:   Imagine you're given an array of integers, let's call it nums . Your task is to create a new array where the value at index i in this new array is the product of all the elements in nums , except the one at index i . In other words, you're calculating the product of all the elements to the left of nums[i] and the product of all the elements to the right of nums[i] , and then multiplying these two products to get the final value at index i ...
Post a Comment
Read more

Day 9 - Challenge 2 - Reverse Linked List

Reversing a Singly Linked List in JavaScript: An In-Place Approach Introduction:   Singly linked lists are fundamental data structures in computer science that consist of a sequence of nodes, each containing data and a reference to the next node in the list. Reversing a singly linked list is a classic problem that challenges programmers to manipulate pointers effectively to achieve the desired outcome. In this blog post, we'll explore the problem of reversing a singly linked list using an in-place approach and provide a step-by-step solution in JavaScript. Problem Statement:   Given the head of a singly linked list, our task is to reverse the list in-place and return its new head. In other words, we need to modify the pointers of the nodes in such a way that the direction of the linked list is reversed. Solution Approach:   To solve this problem, we will iterate through the linked list while maintaining three pointers: previous , current , and next . The previous pointer...
Post a Comment
Read more

Day 8 - Challenge 2 - Move Zeroes to the End

Moving Zeroes to the End: A JavaScript Solution Introduction:   When working with arrays, there are often times when we need to manipulate their elements to achieve a specific goal. One common problem is moving all zeroes to the end of an array while keeping the order of non-zero elements unchanged. In this blog post, we will explore an elegant solution to this problem using JavaScript. We'll discuss the problem statement, the approach we'll take, and provide a step-by-step guide to implementing the solution. The Problem:   Given an array of integers, the task is to move all zeroes to the end of the array while maintaining the relative order of the non-zero elements. This means that after rearranging the array, all the zeroes should be at the end, and the order of the non-zero elements should remain the same. The Approach:   To solve this problem, we can utilize a two-pointer approach. We'll maintain two pointers, one for iterating through the array and another for keepin...
Post a Comment
Read more