[DP : 동적계획법] 최대연속부분수열

 

 

{33, 36, -73, 15, 43, -17, 36, -28, -1, 21}

 

1단계 : 배열 초기화

//초기화
public static void calculate_max(int[] s, int n){

  for(int i=1; i < n; i++){
  	System.out.println("c[" + i + "] = max( s["+i+"],  (s[" + i + "] + c[" + (i-1) + "] ) )");
  	c[i] = max( s[i] , (s[i] + c[i-1]) );
  }


  System.out.println();
  System.out.printf("a[] : ");
  view1(a);
  System.out.printf("c[] : ");
  view1(c);
}


c[1] = max( s[1], c[0] )
c[2] = max( s[2], c[1] )
c[3] = max( s[3], c[2] )
c[4] = max( s[4], c[3] )
c[5] = max( s[5], c[4] )
c[6] = max( s[6], c[5] )
c[7] = max( s[7], c[6] )
c[8] = max( s[8], c[7] )
c[9] = max( s[9], c[8] )

a[] : 33 36 -73 15 43 -17 36 -28 -1 21 
c[] : 0 36 -37 15 58 41 77 49 48 69 0 

 

 

 

 

package org.kyhslam.algo;

public class c20200618 {


    static int[] a = {33, 36, -73, 15, 43, -17, 36, -28, -1, 21};
    static int[] c = new int[10];

    public static int max_consecutive_sum(int[] s, int n){

        int i,j,k, max_sum = s[0];
        int sum =0;

        for(i=0; i < n; i++){
            sum = 0;
            for(j=i; j<n; j++){
                sum += s[j];
                if(sum > max_sum){
                    max_sum = sum;
                }
            }
        }

        return max_sum;
    }


    public static int find_max_consecutive_sum(int s[], int n){

        if(n == 1){
            return s[0];
        }else{
            return max(c[n-1], find_max_consecutive_sum(s, n-1));
        }
    }

    public static int max(int n, int m){
        if(n > m){
            return n;
        }else{
            return m;
        }
    }


    //초기화
    public static void calculate_max(int[] s, int n){

        for(int i=1; i < n; i++){
            System.out.println("c[" + i + "] = max( s["+i+"],  (s[" + i + "] + c[" + (i-1) + "] ) )");
            c[i] = max( s[i] , (s[i] + c[i-1]) );
        }

        System.out.println();


        System.out.printf("a[] : ");
        view1(a);
        System.out.printf("c[] : ");


        view1(c);
    }

    public static void view1(int[] arr){
        for(int k=0; k < arr.length; k++){
            System.out.printf(arr[k] + " ");
        }
        System.out.println("");
    }

    public static void view2(int [][] arr){
        for(int i=0; i < arr.length; i++){

            for(int j=0; j < arr[i].length; j++){
                System.out.printf(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {

        //System.out.println(max_consecutive_sum(a, a.length));
        calculate_max(a, a.length);
        System.out.println(find_max_consecutive_sum(a, a.length));

    }
}