📊

Maximum Subarray Sum Problem

Jul 21, 2024

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

Array (a): Contains 7 elements, index ranges from 0 to 6
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

Understand the problem: Initial steps involve conceptualizing and visualizing the problem.
Brute-force solution: Direct approach to understand the basic logic
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.

Full transcript