Scribd
Upload
2 views3 pages

Dsa Problems

The document discusses the Maximum Subarray Sum problem and presents two approaches: a brute force method and Kadane’s Algorithm. The brute force approach generates all possible subarrays and calculates their sums with a time complexity of O(N²), while Kadane’s Algorithm optimally maintains a running sum and resets it when negative, achieving a time complexity of O(N). Java code examples for both methods are provided along with their respective complexities.

Uploaded by

anil23hr1a0547
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Dsa Problems

The document discusses the Maximum Subarray Sum problem and presents two approaches: a brute force method and Kadane’s Algorithm. The brute force approach generates all possible subarrays and calculates their sums with a time complexity of O(N²), while Kadane’s Algorithm optimally maintains a running sum and resets it when negative, achieving a time complexity of O(N). Java code examples for both methods are provided along with their respective complexities.

Uploaded by

anil23hr1a0547
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Problem: Maximum Subarray Sum (Kadane’s Algorithm)

📌 Question

Given an integer array nums, find the contiguous subarray (containing


at least one number) which has the largest sum and return its sum.

🧾 Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation:

Subarray [4, -1, 2, 1] has maximum sum = 6

Brute Force Approach

💡 Idea

 Generate all possible subarrays

 Calculate sum for each

 Track maximum sum

✅ Java Code (Brute Force)

class Solution {

public int maxSubArray(int[] nums) {

int n = [Link];

int maxSum = Integer.MIN_VALUE;

for(int i = 0; i < n; i++) {

int sum = 0;

for(int j = i; j < n; j++) {

sum += nums[j];

maxSum = [Link](maxSum, sum);

}
}

return maxSum;

Complexity (Brute Force)

 Time Complexity → O(N²)

 Space Complexity → O(1)

👉 Because we check every subarray.

🚀 Optimal Approach (Kadane’s Algorithm)

💡 Idea

Key Observation

If current running sum becomes negative:


👉 It will reduce future sums
👉 So reset it to 0

Steps

1. Maintain currentSum

2. Maintain maxSum

3. Add each element to currentSum

4. Update maxSum

5. Reset currentSum if it becomes negative

✅ Java Code (Optimal)

class Solution {

public int maxSubArray(int[] nums) {

int currentSum = 0;

int maxSum = nums[0];


for(int num : nums) {

currentSum += num;

maxSum = [Link](maxSum, currentSum);

if(currentSum < 0) {

currentSum = 0;

return maxSum;

⏱ Complexity (Optimal)

 Time Complexity → O(N)

 Space Complexity → O(1)

You might also like