C# || Maximum Subarray – How To Find Largest Sum In Contiguous Subarray Using C#
The following is a module with functions which demonstrates how to find the largest sum in a contiguous subarray using C#.
1. Max Sub Array – Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
2. Max Sub Array – Solution
The following is a solution which demonstrates how to find the largest sum in a contiguous subarray.
This solution uses Kadane’s algorithm to find the result.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// ============================================================================ // Author: Kenneth Perkins // Date: Dec 2, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find maximum sum in contiguous subarray // ============================================================================ public class Solution { public int MaxSubArray(int[] nums) { var result = nums[0]; var current = result; for (int index = 1; index < nums.Length; ++index) { current = Math.Max(nums[index], nums[index] + current); result = Math.Max(result, current); } return result; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
6
1
23
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply