TLE酒店（spoj）

Question

我正在做一个spoj的问题，我试图做到这一点，但我总是得到TLE（时间限制过期） 的问题是Hotels。这是我的代码，请你告诉我优化它的方法。

#include<stdio.h> 

int main() 
{ 
    unsigned long long int a,b,i; 
    scanf("%llu %llu",&a,&b); 
    unsigned long long int arr[a]; 
    for(i=0;i<a;i++) 
    { 
     scanf("%llu",&arr[i]); 
    } 


     unsigned long long int d; 
     unsigned long long int k,z=0; 
    for(i=0;i<a;i++) 
    { 
     d = arr[i]; 
     for(k=i+1;k<a+1;k++) 
     { 
      if (d<b) 
      { 
       if(z<d) 
       z = d; 
      } 
      else 
      if(d==b) 
      { 
       z = d; 
       break; 
      } 
      else 
      break; 
      d = d + arr[k]; 
     } 
     if(d==b) 
     break; 
    } 
    printf("%llu",z); 
    return 0; 
} 

在

此一样，如果输入5 12，这五个是2 1 3 4 5使12然后我这样做： 第i个比较12 2，然后2 + 1，则2 + 1 + 3等到5后它比较12到1，1 + 3，1 + 3 + 4 ..这样，我只采取连续和突破，当我发现等于12，否则它继续到最后。

亚太区首席技术官Matt

Answer 1

没有必要为你的解释after it goes to 5 it compares 12 to 1 , 1+3 , 1+3+4 .. and in this way说，再次重新启动。仔细看看你的方法，你重新计算一个子阵列的总和。例如 - 当您在做2+1+3+4时，您已经计算了子阵列1+3+4的总和。因此还有一些优化的范围。

在告诉确切的解决方案之前，我希望您先尝试一下。另外作为一个提示，请参阅以下问题Find subarray with given sum。

编辑：为未来目的共享完整的解决方案。

#include<stdio.h> 

/* Returns the maximum possible sum less than or equal to the gieven sum */ 
int subArraySum(int arr[], int n, int sum) 
{ 
    /* Initialize curr_sum as value of first element 
    and starting point as 0 */ 
    int curr_sum = arr[0], max_sum = 0, start = 0, i; 

    /* Add elements one by one to curr_sum and if the curr_sum exceeds the 
    sum, then remove starting element */ 
    for (i = 1; i <= n; i++) 
    { 
     // If curr_sum exceeds the sum, then remove the starting elements 
     while (curr_sum > sum && start < i-1) 
     { 
      curr_sum = curr_sum - arr[start]; 
      start++; 
     } 

     //keep track of the maximum sum so far. 
     if (max_sum < curr_sum) 
      max_sum = curr_sum; 

     curr_sum = curr_sum + arr[i]; 
    } 

    return max_sum; 
} 

//驱动程序来测试上述功能

int main() 
{ 
    int arr[] = {7, 3, 5, 6}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int sum = 9; 
    printf("Max Sum = %d\n", subArraySum(arr, n, sum)); 
    return 0; 
}