Skip to content

Instantly share code, notes, and snippets.

@marcellodesales
Last active November 22, 2021 18:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save marcellodesales/70973206ca8849ddc9263d11d4f15a33 to your computer and use it in GitHub Desktop.
Save marcellodesales/70973206ca8849ddc9263d11d4f15a33 to your computer and use it in GitHub Desktop.
Solution to the problem of the longest subarray sum... That is, the two ascending... Executable version: https://onlinegdb.com/jYaDXgI5T More information at https://leetcode.com/problems/maximum-ascending-subarray-sum/
/**
* @author Marcello.DeSales@gmail.com
*
* Solution to the problem of the longest subarray sum... That is, the two ascending arrays
* [10,20,30,5,10,50] = 65 [5,10,50]
* [12,17,15,13,10,11,12] = 33. [10,11,12]
**/
public class Main {
public static void main(String[] args) {
int[] nums = new int[]{12,17,15,13,10,11,12};
int maxComputed = computeSum(nums);
System.out.println("value: " + maxComputed);
if (maxComputed == 65) {
System.out.println("Success");
}
}
private static int computeSum(int[] nums) {
if (nums.length == 1) return nums[0];
int currentSum = 0;
leftWindow: for (int left = 0; left < nums.length - 1; left++) {
int leftValue = nums[left];
// the local sum is already the left side
int localSum = leftValue;
for (int right = left + 1; right < nums.length; right++) {
int rightValue = nums[right];
if (leftValue < rightValue) {
// sum is already the left side
localSum += rightValue;
} else if (right == nums.length - 1) {
// When we hit the right side of the window, we know we don't have subarrays
currentSum = currentSum >= localSum ? currentSum : localSum;
break leftWindow;
} else {
// When the value is smaller, we know we don't have an ascending sequence anymore
// The left side turns to be the next value of the right side
left = right - 1;
break;
}
leftValue = nums[right];
}
// As the current local subarray sum now is found, the currentSum can be compared with the previous
currentSum = currentSum >= localSum ? currentSum : localSum;
localSum = 0;
}
return currentSum;
}
}
[10,20,30,5,10,50]
value: 65
Success
Process finished with exit code 0
[12,17,15,13,10,11,12]
value: 33
Success
Process finished with exit code 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment