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)

Problem Explanation: Given an array, the task is to find the subarray with the maximum sum. The brute force approach checks all possible subarrays to find the maximum sum.

Approach:

• Iterate over all subarrays.

• Calculate the sum of each subarray.

• Keep track of the maximum sum.

Code Example:

public class MaxSubarraySum {
    public static int maxSubarraySum(int[] arr) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int currentSum = 0;
                for (int k = i; k <= j; k++) {
                    currentSum += arr[k];
                }
                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 (Brute Force): " + maxSubarraySum(arr));
    }
}

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

---

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