Chapter 9: Arrays (Part 2) | DSA with Java

Hello readers! I'm Rohit Gawande, and welcome back to my blog series "DSA with Java", where we dive deep into Data Structures and Algorithms using Java. In this post, we'll be exploring some crucial array-based problems. We'll start with different approaches for solving the Maximum Subarray Sum problem, then move on to tackling the famous Trapping Rainwater Problem, and finally, the Best Time to Buy and Sell Stock problem.

This is Part 2 in the array series, and I will guide you through various techniques like brute force, prefix sum, Kadane’s algorithm, and more, using Java code examples.

---

Table of Contents:

1. Max Subarray Sum - I (Brute Force)

2. Max Subarray Sum - II (Prefix Sum)

3. Max Subarray Sum - III (Kadane’s Algorithm)

4. Trapping Rainwater Problem

5. Best Time to Buy and Sell Stock

6. Assignment Questions

1. Max Subarray Sum - I (Brute Force)

In this , we’ll tackle the Max Subarray Sum problem using the Brute Force approach. The goal of this problem is to find the maximum sum of any subarray within a given array. Let’s break this down step by step.

Problem Explanation: Given an array arr[], the task is to find the subarray with the maximum sum(a contiguous sequence of elements in the array).. The brute force approach checks all possible subarrays to find the maximum sum.

Example

For the input array:

arr = [1, -2, 6, -1, 3]

Possible subarrays are:

• [1], [1, -2], [1, -2, 6], [1, -2, 6, -1], [1, -2, 6, -1, 3]

• [-2], [-2, 6], [-2, 6, -1], [-2, 6, -1, 3], and so on...

We want to determine the subarray that produces the largest sum.

---

Brute Force Approach

We use three nested loops:

1. Outer Loop (i): Marks the start of the subarray.

2. Middle Loop (j): Marks the end of the subarray.

3. Inner Loop (k): Iterates through the elements of the subarray to calculate its sum.

---

Code Explanation

Here’s the code:

public class Max_Subarray_Sum {
    // Brute Force Approach
    public static void printSubArSum(int arr[]) {
        int currSum = 0;
        int maxSum = Integer.MIN_VALUE; // Initialize maxSum with the smallest possible value

        // Iterate over all possible subarrays
        for (int i = 0; i < arr.length; i++) { // Start index of subarray
            for (int j = i; j < arr.length; j++) { // End index of subarray
                currSum = 0; // Reset currSum for each new subarray
                for (int k = i; k <= j; k++) { // Traverse the subarray
                    currSum += arr[k]; // Add each element to currSum
                }

                // Print the current subarray sum
                System.out.print("Current Sum: " + currSum + " ");

                // Update maxSum if currSum is greater
                if (maxSum < currSum) {
                    maxSum = currSum;
                }
            }
        }

        // Print the results
        System.out.println();
        System.out.println("Max Sum: " + maxSum);
    }

    public static void main(String[] args) {
        int arr[] = {1, -2, 6, -1, 3};
        printSubArSum(arr); // Function call
    }
}

---

Dry Run: Step-by-Step Execution

You are correct! The maximum sum in the given array [1, -2, 6, -1, 3] is indeed 8, not 7. Let me correct the explanation and walk through it again step by step:

---

Correct Dry Run: Step-by-Step Execution

Input:

arr = [1, -2, 6, -1, 3]

Iteration 1 (i = 0):

• Subarrays: [1], [1, -2], [1, -2, 6], [1, -2, 6, -1], [1, -2, 6, -1, 3]

• Current sums:

  • [1] → 1

  • [1, -2] → 1 + (-2) = -1

  • [1, -2, 6] → 1 + (-2) + 6 = 5

  • [1, -2, 6, -1] → 1 + (-2) + 6 + (-1) = 4

  • [1, -2, 6, -1, 3] → 1 + (-2) + 6 + (-1) + 3 = 7

• Max Sum so far: 7

Iteration 2 (i = 1):

• Subarrays: [-2], [-2, 6], [-2, 6, -1], [-2, 6, -1, 3]

• Current sums:

  • [-2] → -2

  • [-2, 6] → -2 + 6 = 4

  • [-2, 6, -1] → -2 + 6 + (-1) = 3

  • [-2, 6, -1, 3] → -2 + 6 + (-1) + 3 = 6

• Max Sum so far: 7

Iteration 3 (i = 2):

• Subarrays: [6], [6, -1], [6, -1, 3]

• Current sums:

  • [6] → 6

  • [6, -1] → 6 + (-1) = 5

  • [6, -1, 3] → 6 + (-1) + 3 = 8

• Max Sum so far: 8

Iteration 4 (i = 3):

• Subarrays: [-1], [-1, 3]

• Current sums:

  • [-1] → -1

  • [-1, 3] → -1 + 3 = 2

• Max Sum so far: 8

Iteration 5 (i = 4):

• Subarray: [3]

• Current sum:

  • [3] → 3

• Max Sum so far: 8

---

Final Output:

Max Sum: 8

---

---

Advantages of the Brute Force Approach

1. Simplicity: Easy to understand and implement.

2. Exhaustive Search: Evaluates all possible subarrays, guaranteeing accuracy.

---

Disadvantages of the Brute Force Approach

1. Inefficient: Has a time complexity of O(n^3) due to three nested loops.

2. Not Scalable: Becomes impractical for large arrays.

---

What’s Next?

While the brute force approach is a good starting point, we can optimize it significantly using:

1. Prefix Sum: Reduces the time complexity to O(n^2).

2. Kadane’s Algorithm: Achieves an efficient O(n)O(n) solution.

---

2. Max Subarray Sum - II (Prefix Sum)

Problem Explanation: A more optimized approach is to use the prefix sum. The prefix sum is an array that stores the cumulative sum of the elements from the start of the array to each position.

Approach:

• First, calculate the prefix sum array.

• Use the prefix sum to compute the sum of any subarray in constant time.

Code Example:

public class MaxSubarraySumPrefix {
    public static int maxSubarraySum(int[] arr) {
        int n = arr.length;
        int[] prefix = new int[n];
        prefix[0] = arr[0];

        // Calculating prefix sum array
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }

        int maxSum = Integer.MIN_VALUE;

        // Calculating subarray sum using prefix sum array
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int currentSum = i == 0 ? prefix[j] : prefix[j] - prefix[i - 1];
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, -2, 3, 4, -1, 2, 1, -5, 4};
        System.out.println("Max Subarray Sum (Prefix Sum): " + maxSubarraySum(arr));
    }
}

Time Complexity: O(n^2)
Space Complexity: O(n)

---

3. Max Subarray Sum - III (Kadane’s Algorithm)

Problem Explanation: Kadane's Algorithm provides an optimal solution to the maximum subarray sum problem. It works by maintaining the maximum sum of subarrays ending at each position.

Approach:

• Initialize two variables: currentSum (to store the sum of the current subarray) and maxSum (to store the maximum sum found so far).

• Traverse the array and decide whether to extend the current subarray or start a new one.

Code Example:

public class MaxSubarrayKadane {
    public static int maxSubarraySum(int[] arr) {
        int maxSum = arr[0];
        int currentSum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, -2, 3, 4, -1, 2, 1, -5, 4};
        System.out.println("Max Subarray Sum (Kadane's Algorithm): " + maxSubarraySum(arr));
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

---

4. Trapping Rainwater Problem

Problem Explanation: Given an array of non-negative integers where each element represents the height of a bar, the task is to calculate how much water can be trapped between the bars after rainfall.

Approach:

• For each element, find the maximum height on the left and right.

• The water trapped on top of each bar is the minimum of the maximum heights on the left and right minus the height of the bar.

Code Example:

public class TrappingRainWater {
    public static int trap(int[] height) {
        int n = height.length;
        if (n <= 2) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        // Calculating left max for each element
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // Calculating right max for each element
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int totalWater = 0;

        // Calculating trapped water for each element
        for (int i = 0; i < n; i++) {
            totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return totalWater;
    }

    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("Total Water Trapped: " + trap(height));
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

---

5. Best Time to Buy and Sell Stock

Problem Explanation: Given an array where each element represents the price of a stock on a given day, the task is to find the maximum profit that can be made by buying and selling the stock once.

Approach:

• Traverse the array and keep track of the minimum price so far.

• At each step, calculate the potential profit and update the maximum profit if needed.

Code Example:

public class BestTimeToBuySellStock {
    public static int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;

        int minPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println("Max Profit: " + maxProfit(prices));
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

---

Assignment Questions

1. Find the maximum product of a subarray.

   • Use a similar approach to Kadane’s Algorithm but account for the effect of negative numbers.

2. Find the smallest subarray with a sum greater than a given value.

   • Implement a sliding window approach.

3. Check if there exists a subarray with a sum equal to 0.

   • Use a HashMap to store cumulative sums.

---

Related Posts in My Series:

DSA in Java Series:

• Chapter 2: Operators in Java – Learn about the different types of operators in Java, including arithmetic, relational, logical, and assignment operators, along with examples to understand their usage.

• Chapter 33: Trie in Java – Explore the implementation and use of Trie data structure in Java, a powerful tool for handling strings, with practical coding examples.

Other Series:

• Full Stack Java Development – Master the essentials of Java programming and web development with this series. Topics include object-oriented programming, design patterns, database interaction, and more.

• Full Stack JavaScript Development – Become proficient in JavaScript with this series covering everything from front-end to back-end development, including frameworks like React and Node.js.

---

Connect with Me
Stay updated with my latest posts and projects by following me on social media:

• LinkedIn: Connect with me for professional updates and insights.

• GitHub: Explore my repositories and contributions to various projects.

• LeetCode: Check out my coding practice and challenges.

Your feedback and engagement are invaluable. Feel free to reach out with questions, comments, or suggestions. Happy coding!

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast