Print Maximum Sum Subarray
Greedy & Kadane's Algorithm DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Find the contiguous subarray in a given integer array with the largest sum (Maximum Subarray Problem), Arrays, Subarray, Time Complexity, Space Complexity, Kadane's Algorithm, space complexity, brute force, prefix sum, general programming, kadane's algorithm, time complexity analysis, array indexing, Subarray Index Tracking.
Given an integer array arr, find the contiguous subarray (containing at least one number) which has the largest sum. Return its sum and print the subarray. 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, which gives a positive sum of 1.