Find Maximum Subarray Sum

Posted in

Find Maximum Subarray Sum
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    Problem

    The objective is to find the elements of a continuous subarray nums of integers that have the highest sum given an array.

    Brute force approach

    The naïve method is to produce all possible subarrays and then display the subarray with the highest sum. This will take O(N2) time which is not efficient.

    Efficient approach

    The aim is to utilise Kadane's Algorithm to discover the largest subarray sum, record the starting and ending indexes of the subarray with the highest sum, and then print the subarray from starting index to the ending index. The steps are as follows: Set the three variables end , curr , and Max to the first value in the input array.

    Starting with index (say) 0, change curr to max( nums [i], nums [i] + Max ) and Max , and set end to i only if curr > Max . To get the start index, iterate from end to the left, decrementing the value of Max until it equals 0 . The start index is the point at which it becomes zero.

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    void maxSubarray(vector<int>& nums)
    {
        // Initialize curr and Max
        int end, curr = nums[0];
        int Max = nums[0];
    
        // Iterate for all the elements for maximum sum
        for (int i = 1; i < nums.size(); ++i) 
        { 
             curr = max(nums[i], nums[i] + curr); 
             // Check if curr is greater 
             // than Max 
             if (curr > Max) 
            {
                Max = curr;
                end = i;
            }
        }
    
        int start = end;
    
        // Traverse in left direction
        while (start >= 0) {
    
            Max -= nums[start];
    
            if (Max == 0)
                break;
    
            // decrement the start index
            start--;
        }
        for (int i = start;
            i <= end; ++i) {
    
            cout << nums[i] << " ";
        }
    }
    
    int main()
    {
        vector<int> nums
            = { 1, 2, 3, -4};
        maxSubarray(nums);
    }
    

    Output

    1 2 3

    Python Programming

    def maxSubarray(nums):
        
        # Initialize curr and Max
        curr = nums[0]
        Max = nums[0]
    
        # Iterate for all the elements
        for i in range(1, len(nums)):
            curr = max(nums[i], nums[i] + curr)
    
            # Check if curr is greater
            # than Max
            if (curr > Max):
                Max = curr
                end = i
        
        start = end
    
        # Traverse in left direction
        while (start >= 0):
            Max -= nums[start]
    
            if (Max == 0):
                break
    
            # Decrement the start index
            start -= 1
        for i in range(start, end + 1):
            print(nums[i], end = " ")
    arr = [1, 2, 4, -5]
    maxSubarray(arr)

    Output

    1 2 4
    

    C# Programming

    using System;
    using System.Collections.Generic;
    class Solution{
    
    static void maxSubarray(List<int> nums)
    {
        // Initialize curr and Max
        int end = 0, curr = nums[0];
        int Max = nums[0];
    
        // Iterate for all the elements
        for (int i = 1; i < nums.Count; ++i) 
        { 
            curr = Math.Max(nums[i], nums[i] + curr); 
           // Check if curr is greater 
           // than Max 
           if (curr > Max)
           {
              Max = curr;
              end = i;
            }
        }
    
        int start = end;
    
        // Traverse in left direction
        while (start >= 0)
        {
        Max -= nums[start];
    
        if (Max == 0)
            break;
    
        // decrement the start index
        start--;
        }
        for(int i = start; i <= end; ++i)
        {
        Console.Write(nums[i] + " ");
        }
    }
    
    public static void Main(String[] args)
    {
        List<int> nums = new List<int>();
        nums.Add(1);
        nums.Add(2);
        nums.Add(-1);
        nums.Add(3);
        maxSubarray(nums);
    }
    }
    

    Output

    1 2 -1 3

    People are also reading:

    Leave a Comment on this Post

    0 Comments