Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C#

Challenge 11: Maximum Sum Subarray

Explore how to determine the maximum sum subarray within an unsorted integer array, including negative values. Learn to develop efficient algorithms beyond brute force to solve this common coding challenge using C#.

We'll cover the following...

Maximum subarray sum: An introduction

Given an unsorted array AA, the maximum sum subarray is the subarray (contiguous elements) from AA for which the sum of the elements is maximum. In this challenge, find the sum of the maximum sum subarray. This problem is trick because the array might have negative integers in any position. Therefore, you have to cater to those negative integers while choosing the continuous subarray with the largest positive values.

Here is an example:

In the above slides, you are showing a “brute force” approach to solving this problem. You are computing the sum of all possible subarrays to find the maximum. Your task is to come up with a more efficient technique to solve this problem.

Problem statement

Given an integer array and its size, return the maximum subarray sum. The array may contain both positive and negative integers and is unsorted.

Input

int maxSumArr(int []arr, int arrSize)

Output

The output is an integer value equal to the maximum sum of subarray found in arr.

Sample input

arr = {1, 7, -2, -5, 10, -1}

Sample output

11

Coding exercise

Take a close look, and design a step-by-step algorithm before jumping on to the implementation. This problem is designed for your practice. Try to solve it on your own first. If you get stuck, you can always refer to the solution provided in the solution review section. Good luck!

C#
class Solution
{
   public static int maxSumArr(int []arr, int arrSize) 
   {
      // Write your code here
      return -1;  
   } 
}