Java Coding Test Course, Finding Continuous Sum

Problem Description

This is a problem of finding the sum of contiguous subarrays in a given integer array.
This type of problem frequently appears in algorithm problem-solving and can be
applied in interviews or coding tests.

Problem Definition:
Given an array of integers nums, answer the following two questions:

  1. Calculate and return the sum of all contiguous subarrays of the given array.
  2. Calculate and return the sum of the largest contiguous subarray.

Problem Solving Approach

To solve this problem, we can utilize a specific algorithm.
In particular, using “Kadane’s algorithm” allows us to efficiently find the sum of the largest contiguous subarray.

Kadane’s Algorithm is a type of dynamic programming that finds the optimal solution
by storing necessary values in memory while traversing the array only once.
The idea of this algorithm is to keep track of the maximum sum up to the current point and update it
as new elements are added.

Problem Solving Steps

Step 1: Conceiving the Basic Idea

To find the sum of contiguous subarrays, we first need to calculate the maximum sum at the current index.
This is determined by comparing the current array element with the maximum sum up to the previous point.

Step 2: Implementing the Algorithm

Now, let’s write the code to solve the problem using the Java language.
Below is an example code implementing the algorithm. 


public class ContinuousSum {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Sum of the largest contiguous subarray: " + maxSubArray(nums));
    }

    public static int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
}

Step 3: Complexity Analysis

The above algorithm has a time complexity of O(n) and a space complexity of O(1).
This is very efficient in terms of time since it traverses the array only once.

Examples and Testing

To test the provided algorithm, we can use several examples to validate the results.
Below are examples for various inputs.

  • Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → Output: 6
  • Input: [1] → Output: 1
  • Input: [5, 4, -1, 7, 8] → Output: 23
  • Input: [-1, -2, -3] → Output: -1

Conclusion

Today, we solved the problem of finding contiguous sums using Kadane’s algorithm.
This is a type frequently encountered in algorithm problem-solving, and
solving problems efficiently is very important.
Engage with various problems to enhance your understanding of algorithms and data structures.