August 10, 2022
Here is the link.
C# | Quick learner | Four solutions | My progress
March 3, 2020 - Aug 10, 2022
Introduction
I like to share my four practice from 2018 to 2021. Hard work beats talent. Keep going, work hard. Practice makes perfect.
Four practices | One with two upvotes
The following is my latest practices with two upvotes:
- Latest practice on Jan. 12, 2021, two upvotes, C# - prefix sum. Here is the link.
Three practices | Continue to make improvements
I also had three practices from 2018 to 2020. It is better to keep the records and continue to make improvements.
- C# work on prefix sum - fix a bug written in mock interview on March 1, 2020. Here is the link. Practice date: March 1, 2020
- C# work on prefix sum - this one is more complicated. Should be simplified. Here is the link. Practice date: March 3, 2020
- C# work on dynamic programming, optimal time complexity O(N). Here is the link. Practice date: August 28, 2018
I learn to practice the aglorithm during mock interview from 2018 to 2021 as a mock interviewer.
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.
Solution 1 | C# - prefix sum
Jan. 12, 2021
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
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.
The idea is to save prefix sum's smallest value, so that every iteration from left to right the maximum contiguous subarray's sum can be found easily.
public class Solution {
public int MaxSubArray(int[] nums) {
if(nums == null || nums.Length == 0)
return 0;
var minPrefixSum = 0;
var length = nums.Length;
var largestSum = Int32.MinValue;
var prefixSum = 0;
var foundOne = false;
for(int i = 0; i < length; i++)
{
var current = nums[i];
prefixSum += current;
var diff = prefixSum - minPrefixSum;
if(diff > largestSum)
{
largestSum = diff;
}
if(prefixSum < minPrefixSum)
{
minPrefixSum = prefixSum;
}
}
return largestSum;
}
}
July 5, 2022 | 10 Downvotes | Make improvements
I came cross this discuss post with down votes -10, so I quickly learn the lessons. I like to make improvements in terms of writing skills and problem solving skills.
I can write better C# code, but I still like to keep those past practice in order to encourage myself work hard, and learn to write a simple discuss post and then learn to make improvements.
Thanks for continuous support.
Solution 2 | C# work on prefix sum
I chose to share my practice solution during my mock interview on March 1, 2020.
Case study
Input: [1, 4, -100, 1]
The idea is to use prefix sum to find maximum subarray. We like to brute force end position for all positions from 0 to length - 1.
We deliberately define three variables:
sum - it is prefix sum
minValue - it is the minimum of prefix sums
maxSubArraySum - for each end position, it will be updated if needed.
To make code simple, we like to design a for loop for working on end position in the following:
for (int i = 0; i < length; i++)
So default values for the above three variables are easy to choose as following. But be careful to make corrections to deal with edge case like i = 0.
var sum = 0; // prefix sum default is zero,
var minValue = 0; // prefix sum minimum one is zero
var maxSubArraySum = 0; // this may not be true. For the first element of the array, the variable should be set value correctly.
Input: [1, 4, -100, 1]
sum
[1, 5, -95, -94]
minValue
[0, 0, -95, -95]
maxEndAtI
[1, 5, -95, 1]
maxSubArraySum
[1, 5, 5, 5]
Edge case
The idea is to solve the maximum subarray using prefix sum. In order to write bug-free code, the edge case should be considered when i ==0, maxSubArraySum should not be default value 0 anymore. For example, test case with input [-1], the value should be -1 instead.
Time complexity
O(N), N is the length of the array.
The following C# code passes online judge.
public class Solution {
/// work on test case [1, 4, -100, 1]
public int MaxSubArray(int[] numbers) {
if (numbers == null)
return 0;
var length = numbers.Length;
var sum = 0; // prefix sum
var minValue = 0;
var maxSubArraySum = 0;
// work on end position
for (int i = 0; i < length; i++)
{
var current = numbers[i]; // 1, 4, -100, 1
sum = current + sum; // 1, 5, -95, -94
var maxEndAtI = sum - minValue; // 1 - 0 = 1, 5, -95, 1
// edge case - added after mock interview
if (i == 0)
{
maxSubArraySum = maxEndAtI;
}
if (maxSubArraySum < maxEndAtI ) // 0 < 1, 1 < 5, 5 > -95
{
maxSubArraySum = maxEndAtI; // 1, 5,
}
// update minValue
if (sum < minValue) // 1 > 0, 5 5 > 0 , -95 < 0
{
minValue = sum; // 0, -95
}
}
return maxSubArraySum; // 5 [0,1]
}
}
Solution 3 | Prefix sum | March 3 2020
I like to share my analysis based on my practice and recent mock interview experience.
Case study
If all numbers are positive ones, then all numbers should be included. Otherwise work on prefix sum, and then exclude those negative prefix sum as possible.
If I can work on the above idea, then I should come out the ideas to solve the problem.
The idea is to work on all subarrays ending at index position i from 0 to length - 1.
In the design process, consider the following arrays:
[-1], what is the return? Answer: -1
[1], what is the return? Answer: 1
[1, 2,3, 4], what is the maximum sum of subarray? 10
[1, 2, -4, 4], what is the maximum sum of subarray? 4
My weakness
I am overconfident in mock interview or onsite interview. But it is important to challeng myself to come out simple test cases like [-1], [1], or all positive numbers to challenge my assumptions. I wrote buggy code in my recent mock interview on March 1, 2020.
public class Solution {
public int MaxSubArray(int[] numbers) {
if (numbers == null)
return 0;
var length = numbers.Length;
var prefixSum = numbers[0];
var minPrefixSum = numbers[0];
var maxSubArraySum = numbers[0];
// work on end position
for (int i = 1; i < length; i++)
{
var current = numbers[i];
prefixSum = current + prefixSum;
// all positive numbers, sum
// some negative numbers in between, exclude negative prefix as possible
var maxEndAtI = Math.Max(prefixSum, prefixSum - minPrefixSum);
if (maxSubArraySum < maxEndAtI)
{
maxSubArraySum = maxEndAtI;
}
// update minValue
if (prefixSum < minPrefixSum)
{
minPrefixSum = prefixSum;
}
}
return maxSubArraySum;
}
}
Solution 4 | Dynamic programming | 2018 August 28
I like to share my C# practice. The idea is to apply dynamic programming to calculate the sum of the all subarray starting from index value zero first, and then brute force the end position of each continuous subarray. In order to calculate the maximum value, one variable is used to keep the minimum value of prefix array sum.
In summary there are four steps.
- Preprocess the prefix array sum starting from index 0; time complexity O(N);
- Brute force the end position of subarray
- Keep calculate the minimum sum of prefix array, calculate current maximum
- Get global maximum value
public class Solution {
public int MaxSubArray(int[] nums)
{
if (nums == null)
return 0;
var prefixSum = getPrefixSum(nums);
var minimumSofar = 0;
var max = int.MinValue;
for (int i = 0; i < nums.Length; i++)
{
var current = prefixSum[i];
var currentMax = current - minimumSofar;
max = max < currentMax ? currentMax : max;
minimumSofar = minimumSofar > current ? current : minimumSofar;
}
return max;
}
private static int[] getPrefixSum(int[] nums)
{
var length = nums.Length;
var prefixSum = new int[length];
for (int i = 0; i < length; i++)
{
prefixSum[i] = i > 0 ? prefixSum[i - 1] : 0;
prefixSum[i] += nums[i];
}
return prefixSum;
}
}
No comments:
Post a Comment