C, using max heap , 6ms, dynamic space distribution, but is too long.......


  • 0
    T
    struct buysells
    {
    	int beginDay;
    	int endDay;
    	int buyDay;
    	int sellDay;
    	int increaseProfit;
    };
    typedef struct buysells buysell;
    typedef buysell *buysellpointer;
    
    struct freetimes
    {
    	int startDay;
    	int endDay;
    	int buyDay;
    	int sellDay;
    	int profit;
    };
    typedef struct freetimes freetime;
    typedef freetime * freetimepointer;
    
    void expandBSPHeap(buysellpointer **heap, int *bsppNumLimit)
    {
    	buysellpointer* newheap = (buysellpointer*)malloc(*bsppNumLimit *2 * sizeof(buysellpointer));
    
    	for (int i = 0; i < *bsppNumLimit; i++)
    	{
    		newheap[i] = (*heap)[i];
    	}
    	free(*heap);
    	*heap = newheap;
    	*bsppNumLimit = *bsppNumLimit * 2;
    }
    
    
    void insertBSP(buysellpointer BSP,buysellpointer **heap, int *length, int *bsppNumLimit)
    {
    	if(*length == *bsppNumLimit)
    		expandBSPHeap(heap,bsppNumLimit);
    
    	(*heap)[(*length)++] = BSP;
    	int index = *length-1;
    	buysellpointer tempBSP = BSP;
    	while (index!=0 && (*heap)[(index+1)/2-1]->increaseProfit < tempBSP->increaseProfit )
    	{
    		(*heap)[index] = (*heap)[(index+1)/2-1];
    		index = (index+1)/2 -1;
    	}
    	(*heap)[index] = BSP;
    }
    
    void  deleteBSP(buysellpointer *heap, int *length)
    {
    	if(*length == 0)
    		return;
    	(*length)--;
    	free(heap[0]);
    	heap[0] = heap[*length];
    	buysellpointer tempBSP = heap[*length];
    	int index = 0;
    	int maxChildIndex = 1;
    	while (maxChildIndex < *length)
    	{
    		if(maxChildIndex + 1 < *length)
    			if(heap[maxChildIndex+1]->increaseProfit > heap[maxChildIndex]->increaseProfit)
    				maxChildIndex++;
    		if(heap[maxChildIndex]->increaseProfit > tempBSP->increaseProfit)
    		{
    			heap[index] = heap[maxChildIndex];
    			heap[maxChildIndex] =  tempBSP;
    			index = maxChildIndex;
    			maxChildIndex = (index+1)*2 - 1;
    		}
    		else
    			break;
    	}
    }
    
    void expandFTPHeap(freetimepointer **heap, int *fppNumLimit)
    {
    	freetimepointer* newheap = (freetimepointer*)malloc(*fppNumLimit *2 * sizeof(buysellpointer));
    
    	for (int i = 0; i < *fppNumLimit; i++)
    	{
    		newheap[i] = (*heap)[i];
    	}
    	free(*heap);
    	*heap = newheap;
    	*fppNumLimit = *fppNumLimit * 2;
    }
    
    void insertFTP(freetimepointer FTP,freetimepointer **heap, int *length, int *fppNumLimit)
    {
    
    	if(*length == *fppNumLimit)
    		expandFTPHeap(heap,fppNumLimit);
    
    	(*heap)[(*length)++] = FTP;
    	int index = *length-1;
    	freetimepointer tempFTP = FTP;
    	while (index!=0 && (*heap)[(index+1)/2-1]->profit < tempFTP->profit )
    	{
    		(*heap)[index] = (*heap)[(index+1)/2-1];
    		index = (index+1)/2 -1;
    	}
    	(*heap)[index] = tempFTP;
    }
    
    void  deleteFTP(freetimepointer *heap, int *length)
    {
    	if(*length == 0)
    		return;
    	(*length)--;
    	free(heap[0]);
    	heap[0] = heap[*length];
    	freetimepointer tempFTP = heap[*length];
    	int index = 0;
    	int maxChildIndex = 1;
    	while (maxChildIndex < *length)
    	{
    		if(maxChildIndex + 1 < *length)
    			if(heap[maxChildIndex+1]->profit > heap[maxChildIndex]->profit)
    				maxChildIndex++;
    		if(heap[maxChildIndex]->profit > tempFTP->profit)
    		{
    			heap[index] = heap[maxChildIndex];
    			heap[maxChildIndex] =  tempFTP;
    			index = maxChildIndex;
    			maxChildIndex = (index+1)*2 - 1;
    		}
    		else
    			break;
    	}
    }
    
    
    void findmaxprofit(int prices[],freetimepointer ftp)
    {
    	int minDay = ftp->startDay;
    	ftp->buyDay = minDay;
    	ftp->sellDay = minDay;
    	ftp->profit = 0;
    	for (int i = ftp->startDay+1; i <= ftp->endDay; i++)
    	{
    		minDay = (prices[minDay] > prices[i]) ? i : minDay;
    		if (prices[i] - prices[minDay] > ftp->profit)
    		{
    			ftp->buyDay = minDay;
    			ftp->sellDay = i;
    			ftp->profit = prices[i] - prices[minDay];
    		}
    	}
    }
    
    void findMaxIncreaseProfit(int prices[],buysellpointer bsp)
    {
    	int maxDay = bsp->beginDay;
    	bsp->buyDay = maxDay;
    	bsp->sellDay = maxDay;
    	bsp->increaseProfit = 0;
    	for (int i = bsp->beginDay+1; i < bsp->endDay; i++)
    	{
    		maxDay = (prices[i] > prices[maxDay]) ? i : maxDay;
    		if (prices[maxDay] - prices[i] > bsp->increaseProfit)
    		{
    			bsp->buyDay = i;
    			bsp->sellDay = maxDay;
    			bsp->increaseProfit = prices[maxDay] - prices[i];
    		}
    	}
    
    }
    
    
    int maxProfit(int k, int prices[], int n) {
    
    	int totalProfit=0;
    	int fppNumLimit = 50;
    	freetimepointer *fpp= (freetimepointer*)malloc(fppNumLimit*sizeof(freetimepointer));
    	int fppNum = 0;
    	int bsppNumLimit = 50;
    	buysellpointer *bspp = (buysellpointer*)malloc(bsppNumLimit*sizeof(freetimepointer));
    	int bsppNum = 0;
    
    	fpp[0] = (freetimepointer)malloc(sizeof(freetime));
    	fpp[0]->startDay = 0;
    	fpp[0]->endDay = n-1;
    	findmaxprofit(prices,fpp[0]);
    	if(fpp[0]->profit == 0)
    		return 0;
    	fppNum++;
    
    	for (int i = 0; i < k; i++)
    	{
    		int maxIncreaseProfit =0, maxProfit =  0;
    		if(fppNum)
    			maxProfit = fpp[0]->profit;
    		if(bsppNum)
    			maxIncreaseProfit = bspp[0]->increaseProfit;
    		if(maxIncreaseProfit == 0 && maxProfit==0)
    			return totalProfit;
    		if(maxIncreaseProfit > maxProfit)
    		{
    			buysellpointer tempBSP = bspp[0];
    			buysellpointer tempBSP1 = NULL;
    			if (tempBSP->sellDay -1 > tempBSP->beginDay +1)
    			{
    				tempBSP1 = (buysellpointer)malloc(sizeof(buysell));
    				tempBSP1->beginDay = tempBSP->beginDay;
    				tempBSP1->endDay = tempBSP->sellDay;
    				findMaxIncreaseProfit(prices,tempBSP1);
    				insertBSP(tempBSP1, &bspp, &bsppNum,&bsppNumLimit);
    			}
    			if(tempBSP->endDay -1 > tempBSP->buyDay+1)
    			{
    				tempBSP1 = (buysellpointer)malloc(sizeof(buysell));
    				tempBSP1->beginDay = tempBSP->buyDay;
    				tempBSP1->endDay = tempBSP->endDay;
    				findMaxIncreaseProfit(prices,tempBSP1);
    				insertBSP(tempBSP1, &bspp, &bsppNum,&bsppNumLimit);
    			}
    			if(tempBSP->buyDay -1 > tempBSP->sellDay +1)
    			{
    				freetimepointer tempFTP = (freetimepointer)malloc(sizeof(freetime));
    				tempFTP->startDay = tempBSP->sellDay +1;
    				tempFTP->endDay = tempBSP->buyDay - 1;
    				findmaxprofit(prices, tempFTP);
    				insertFTP(tempFTP,&fpp,&fppNum,&fppNumLimit);
    			}
    			totalProfit += maxIncreaseProfit;
    			deleteBSP(bspp,&bsppNum);
    		}
    		else
    		{
    			freetimepointer tempFTP =  fpp[0];
    			int buyDay = tempFTP->buyDay;
    			int sellDay = tempFTP->sellDay;
    			freetimepointer tempFTP1 = NULL;
    			if(buyDay > tempFTP->startDay + 1)
    			{
    				tempFTP1 = (freetimepointer)malloc(sizeof(freetime));
    				tempFTP1->startDay = tempFTP->startDay;
    				tempFTP1->endDay = buyDay -1;
    				findmaxprofit(prices,tempFTP1);
    				insertFTP(tempFTP1,&fpp,&fppNum,&fppNumLimit);
    			}
    			if(tempFTP->endDay > tempFTP->sellDay + 1)
    			{
    				tempFTP1 = (freetimepointer)malloc(sizeof(freetime));
    				tempFTP1->startDay = tempFTP->sellDay + 1;
    				tempFTP1->endDay = tempFTP->endDay;
    				findmaxprofit(prices,tempFTP1);
    				insertFTP(tempFTP1,&fpp,&fppNum,&fppNumLimit);
    			}
    			if (tempFTP->sellDay-1 > tempFTP->buyDay+1 )
    			{
    				buysellpointer tempBSP = (buysellpointer)malloc(sizeof(buysell));
    				tempBSP->beginDay = tempFTP->buyDay;
    				tempBSP->endDay = tempFTP->sellDay;
    				findMaxIncreaseProfit(prices,tempBSP);
    				insertBSP(tempBSP,&bspp,&bsppNum,&bsppNumLimit);
    			}
    			totalProfit += maxProfit;
    			deleteFTP(fpp,&fppNum);
    		}
    	}
    	return totalProfit;
    }
    

    anyone helps?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.