LeetCode/leet188.cpp at master · ocean1992/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
int *low, *hig;
int count, res ;
int *dp ;

int maxProfit(int k, int* prices, int pricesSize) {
    int mp, lp ;

    low = malloc(sizeof(int)*pricesSize) ;
    hig = malloc(sizeof(int)*pricesSize) ;
    int j = 0 ;
    mp = lp = prices[0] ;
    for(int i=1 ;i<pricesSize ;i++){
        if(prices[i]>=mp){
            mp = prices[i] ;
        }else{
            if(mp>lp){
                low[j] = lp ;
                hig[j] = mp ;
             //   hid[j] = j ;
                j++ ;
            }
            mp = lp = prices[i] ;
        }
    }
    if(mp > lp){
        low[j] = lp ;
        hig[j] = mp ;
        j++ ;
    }
    count = j ;
    //start DP ;
    res = 0 ;
    printf("count = %d\n",count) ;
    if(k>pricesSize){
    	printf("k too large!\n");
    	res = 0 ;
    	for(int i=0 ;i<count ;i++){
    		res += hig[i]-low[i] ;
    	}
    	return res ;
    }

    dp = malloc(sizeof(int)*count) ;
    for(int i=0 ;i<count ;i++){
    	dp[i] = 0 ;
    }
    for(int mk=1 ;mk<=k ;mk++){
    	for(int i=0 ;i<count ;i++){
    		for(int j=i ;j<count-1 ;j++){
    			int temp = hig[j]-low[i] + dp[j+1] ;
    			if(temp > dp[i])
    				dp[i] = temp ;
    		}
    		int temp = hig[count-1]-low[i] ;
    		if(temp > dp[i])
    			dp[i] = temp ;
    	}
    	for(int i=count-2; i>=0 ;i--){
    	    if(dp[i]<dp[i+1])
    	        dp[i] = dp[i+1] ;
    	}
    }
   	for(int i=0 ;i<count ;i++){
   		if(dp[i]>res)
   			res = dp[i] ;
   	}
   	printf("res = %d\n", res) ;
   	return res ;
}