1031. Maximum Sum of Two Non-Overlapping Subarrays

April 21, 2019

Introduction 

It was so painful experience to make the code work. I need to look into how to simplify the code and make it easy to write and less error prone.

Code study

I wrote the code in the contest and spent hours to make the code work. I need to use the debugger to figure out what is wrong.

	public class Solution {
	public int MaxSumTwoNoOverlap(int[] A, int L, int M) {
	var length = A.Length;
	var maxPrefixL = findMaxLPrefix(A, L);
	var maxPrefixM = findMaxLPrefix(A, M);
	var maxSuffixM = findMaxSuffix(A, M);
	var maxsuffixL = findMaxSuffix(A, L);
	var max = 0;
	for (int i = L - 1; i < length - M; i++)
	{
	var current = maxPrefixL[i];
	current += maxSuffixM[i + 1];
	max = max < current ? current : max;
	}
	for (int i = M - 1; i < length - L; i++)
	{
	var current = maxPrefixM[i];
	current += maxsuffixL[i + 1];
	max = max < current ? current : max;
	}
	return max;
	}
	private static int[] findMaxLPrefix(int[] numbers, int L)
	{
	var length = numbers.Length;
	var prefixSum = new int[length];
	var sum = 0;
	for (int i = 0; i < L; i++)
	{
	sum += numbers[i];
	}
	prefixSum[L - 1] = sum;
	var max = sum;
	for (int i = L; i < length; i++)
	{
	var newSum = sum - numbers[i - L];
	newSum += numbers[i];
	max = newSum > max ? newSum : max;
	prefixSum[i] = max;
	sum = newSum; // added after debugging
	}
	return prefixSum;
	}
	/// <summary>
	///
	/// </summary>
	/// <param name="numbers"></param>
	/// <param name="L"></param>
	/// <returns></returns>
	private static int[] findMaxSuffix(int[] numbers, int L)
	{
	var suffixsum = getSuffixSum(numbers, L);
	var length = numbers.Length;
	int max = Int16.MinValue;
	var maxNo = new int[length];
	for(int i = length - 1; i >= 0; i--)
	{
	var current = suffixsum[i];
	max = current > max ? current : max;
	maxNo[i] = max;
	}
	return maxNo;
	}
	private static int[] getSuffixSum(int[] numbers, int L)
	{
	var length = numbers.Length;
	var suffixSum = new int[length];
	var previousSum = 0;
	for (int i = 0; i < L; i++)
	{
	previousSum += numbers[i];
	}
	suffixSum[0] = previousSum;
	for (int i = 1; i + L - 1 < length; i++)
	{
	var newSum = previousSum - numbers[i - 1];
	newSum += numbers[i + L - 1];
	suffixSum[i] = newSum;
	previousSum = newSum; // added after debugging
	}
	return suffixSum;
	}
	}

view raw leetcode1031maximumSum.cs hosted with ❤ by GitHub