Last active
November 22, 2021 18:05
-
-
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/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* @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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
[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