JavaScript Coding Test Course, Calculating the Sum of Consecutive Numbers

The ability to solve algorithm problems is very important in the process of preparing for coding tests. In this post, we will explore a JavaScript coding test problem on the topic of “Calculating the Sum of Consecutive Numbers.” I will explain the process of understanding and solving the problem step by step. This process will help you tackle complex algorithm problems.

Problem Description

You need to calculate the sum of consecutive numbers in a given array. Consecutive numbers refer to two adjacent elements in the array, and their sum can be calculated. However, this problem requires not just finding the sum of two elements, but calculating the sum of all possible consecutive subarrays and finding the maximum sum among them.

Input

  • An integer array arr is given. (1 ≤ arr.length ≤ 10^5)
  • Each element of the array falls within the range of -10^4 ≤ arr[i] ≤ 10^4.

Output

Return the maximum value among the sums of all consecutive subarrays.

Example

Input: arr = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The sum of the continuous subarray [4,-1,2,1] is 6, which is the largest sum.

Problem Approach

To solve this problem, we need an algorithm that can effectively calculate the sum of consecutive subarrays. Here are the steps to follow to solve this problem:

Step 1: Understanding

Clearly understand the requirements of the problem and analyze the cases in which a large sum occurs. For example, if all elements of the array are negative, we need to realize that we should return the largest among them.

Step 2: Choosing an Algorithm

We will use the “Kadane’s Algorithm” to solve this problem. Kadane’s Algorithm is a very efficient algorithm that can find the maximum sum of consecutive subarrays with O(n) time complexity. This algorithm works by tracking the maximum sum so far and deciding whether to include the current element or not.

Step 3: Implementing the Algorithm

Now, let’s implement Kadane’s Algorithm in JavaScript.


function maxSubArray(arr) {
    let maxSoFar = arr[0]; // Maximum value among the sum of all elements
    let maxEndingHere = arr[0]; // Maximum value at the current position

    for (let i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]); // Compare current value and previous sum
        maxSoFar = Math.max(maxSoFar, maxEndingHere); // Update maximum sum
    }

    return maxSoFar;
}

Step 4: Testing

After implementing the function, it should be tested with various input values. Below are some test cases:


console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([5, 4, -1, 7, 8])); // 23
console.log(maxSubArray([-1, -2, -3, -4])); // -1
console.log(maxSubArray([-5, -2, -3, -4, -1])); // -1

Conclusion

In this post, we solved the “Calculating the Sum of Consecutive Numbers” problem using Kadane’s Algorithm. Problems like this frequently appear in coding tests, so it is essential to practice enough. Understanding the algorithm and validating accuracy with various test cases is important. Continuous effort is needed to improve your coding skills by tackling various algorithm problems in the future.