public class MaxSubSequence {    
    public static void main (String[] args) {
        int[] input = new int[]{3,73,-95,42,43,29,-30,-87,74,-53,22,74,-91,-1,-27,-8,-14,26,-67,-74};
        
        int[] fDp = new int[input.length];    //f for dp
        //process first element
        if (input[0] > 0)
            fDp[0] = input[0];
        for (int i = 1;i < input.length;++i){
            if (fDp[i-1]+input[i] > 0)
                fDp[i] = fDp[i-1]+input[i];
            else
                fDp[i] = 0;
        }
        //find the max value in fDp
        int maxSun = 0;
        for (int sum : fDp)
            if (sum > maxSun)
                maxSun = sum;
                
        System.out.println("max sum : " + maxSun);
    }
    
}