You are given an array of positive integers. You must write a program that will return the sum of the maximum sum subsequence of the array, taking int consideration that the integers in the subsequence must be sorted in increasing order.
Input: int[] numbersArray = {2, 89, 5, 6, 88, 8, 11}; Output: 101 Explanation: 2 + 5 + 6 + 88 = 101. |
Solution:
1. static int maxSumIncreasingSubsequence(int[] numbersArray) { 2. int elements = numbersArray.length; 3. int[] result = new int[elements]; 4. 5. System.arraycopy(numbersArray, 0, result, 0, elements); 6. 7. for (int i = 1; i < elements; i++) { 8. for (int j = 0; j < i; j++) { 9. if (numbersArray[i] > numbersArray[j] && 10. result[i] < result[j] + numbersArray[i]) { 11. result[i] = result[j] + numbersArray[i]; 12. } 13. } 14. } 15. 16. Arrays.sort(result); 17. return result[elements - 1]; 18. }