Maximum Subarray Sum (Kadane's Algorithm)
Greedy & Kadane's Algorithm DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Find the contiguous subarray with the largest sum in an integer array (Maximum Subarray Sum Problem), Arrays, Subarray, Time Complexity, Space Complexity, Loops, iterative algorithms, space complexity, brute force, subarray, prefix sum, divide and conquer, kadane's algorithm, time complexity analysis, array indexing, Prefix Sums, Brute-Force Search, Maximum Subarray Sum (Kadane's Algorithm), Iterative Algorithms, Subarray Index Tracking.
Problem Statement Given an integer array arr, find the contiguous subarray (containing at least one number) which has the largest sum. Your task is to return this largest sum and print the subarray itself. Example 1: Input: arr = [ 2,1, 3,4, 1,2,1, 5,4] Output: 6 Explanation: The subarray [4, 1,2,1] has the largest sum = 6. Example 2: Input: arr = [1] Output: 1 Explanation: The array has only one element, and its sum is 1.