Find a maximum sum of a compact subsequence of array elements.
- Difficulty Level: Easy
- Question URL: https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/
- Time Complexity:
Solution:
Solution to Codility's The maximum sum of the Slice problem which is from the Codility Lesson 9: Maximum slice problem and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to find a maximum sum of a compact subsequence of array elements. You can find the question of this MaxSliceSum problem in the Codility website.
package Codility.Lesson9;
import java.util.Arrays;
import java.util.Collections;
public class MaxSliceSum {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] int1 = { 3, 2, -6, 4, 0 };
int result1 = solution(int1);
System.out.println(result1);
}
public static int solution(int[] A) {
// write your code in Java SE 8
int maxEndingPrevious = A[0];
int maxEndingHere = A[0];
int maxSoFar = A[0];
for (int i = 1; i < A.length; i++) {
maxEndingHere = Math.max(A[i], maxEndingPrevious + A[i]);
maxEndingPrevious = maxEndingHere;
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
}