{}
// Online Java Compiler
// Use this editor to write, compile and run your Java code online
import java.util.*;
class Main {
public static void main(String[] args)
{
ArrayList<Integer> reconstructedSoln = new ArrayList<Integer>();
int arr[] = {-3,-2,-1};
int dp[] = new int[arr.length];
dp[0] = arr[0];
int overallMaxVal = dp[0];
int maxIdx = 0;
for(int i=1; i<arr.length; i++)
{
dp[i] = Math.max(arr[i]+dp[i-1], arr[i]);
if(dp[i] > overallMaxVal)
{
overallMaxVal = dp[i];
maxIdx = i;
}
}
System.out.println(overallMaxVal);
System.out.println(maxIdx);
int startVal = overallMaxVal-arr[maxIdx];
reconstructedSoln.add(arr[maxIdx]);
int startIdx = maxIdx-1;
while(startVal>0 && startIdx>=0)
{
reconstructedSoln.add(arr[startIdx]);
startVal = startVal - arr[startIdx];
startIdx--;
}
Collections.reverse(reconstructedSoln);
System.out.println((reconstructedSoln));
}
}