Maximum Subarray Sum Problem

Introduction

• Objective: Find the maximum sum of a subarray
• Context: Subarray problems often appear in various forms. This session focuses on calculating the maximum sum for a subarray.

Problem Explanation

1. Array (a): Contains 7 elements, index ranges from 0 to 6
2. Subarray Size (w): Let’s assume size = 4

Example

• Given Array: [a0, a1, a2, a3, a4, a5, a6]
• Calculating sums for subarrays of size 4:
  • s1: Elements a0 to a3, Sum = 14
  • s2: Elements a1 to a4, Sum = 22
  • s3: Elements a2 to a5, Sum = 20
  • s4: Elements a3 to a6, Sum = 30
• Maximum: From the calculations, s4 (Sum = 30) is the maximum

Logic and Approach

• Basic Approach: Understanding brute-force method before moving to advanced techniques.

Steps

1. Understand the problem: Initial steps involve conceptualizing and visualizing the problem.
2. Brute-force solution: Direct approach to understand the basic logic
3. Set Variables:

• max = -Infinity: Initialize max with smallest value to store highest subarray sum
• Loops to iterate through subarrays and calculate sums

Brute-force Method

• Outer Loop (i): Runs from 0 to length of array - w
  • Inner Loop (j): Runs from i to i + w - 1
    • Calculate current sum for each subarray and compare it with max

int maxSubArraySum(int a[], int n, int w) {
    int max = -Infinity;
    for (int i = 0; i <= n-w; i++) {
        int current = 0;
        for (int j = i; j < i + w; j++) {
            current += a[j];
        }
        if (current > max) {
            max = current;
        }
    }
    return max;
}

Insights

• Calculating up to where i can go: Length of array - subarray size (n-w)
• Time Complexity: Inner and outer loops make it O(n^2), an inefficient approach for larger arrays

Challenges and Optimization

• Performance: Brute-force method is slow for large arrays.
• Sliding Window Technique: Faster approach, discussed in subsequent sessions.

Key Takeaways

• Always understand the problem deeply before jumping to coding.
• Know why optimized methods are needed and their advantages.

Next Steps

• Move to Sliding Window Technique in the next session.
• Develop understanding of how and why optimized methods work.