Why my trivial DP soultion get WA ?


  • -1
    W

    int maxSubArray(int* nums, int numsSize) {

    int table[numsSize][numsSize];
    
    
    int i;
    int j;
    int k;
    int max = -1e9;
    
    
    
    
    if(numsSize == 1)return nums[0];
    
    for(i = 0; i < numsSize; i++){
       for(j = 0; j < numsSize; j++ ){
       	table[i][j] = 0;
       	if(i == j)table[i][j] = nums[i];
       }
    }
    
     
     for(i = 1; i < numsSize; i++){
        int sum = 0;
        int len = 1+i;
       for(j = 0; j <= numsSize-len; j++ ){
       	
       	        k = i+j;
      
                table[j][k] = table[j][k-1] + table[j+1][k] - table[j+1][k-1];
    
       }
    }
    
     return max;
    

    }


  • 0
    G

    Uses too much memory and takes too long.
    Probably the least efficient code I've ever seen.
    Even if you want to use an extra 2D array to calculate all the options, there's definitely no need to run over it twice.
    In addition, you are calculating sums more than once.
    Also the way you compute each value is way more complicated than it should.


Log in to reply
 

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