Find Maximum Subarray Sum

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:

• Longest subarray with sum as K
• Find whether an array is subset of another array
• Print a given matrix in spiral form
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Dutch National Flag Problem
• Majority Element
• Minimum Edit Distance
• WAP to Print Triangle Using * Character
• Bottom View of a Binary Tree
• Subset Sum Problem