你能构造出连续值的最大数目

你能构造出连续值的最大数目

给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以 构造 出 x 。

请返回从 0 开始（包括 0 ），你最多能 构造 出多少个连续整数。

你可能有多个相同值的硬币。

示例 1：

输入：coins = [1,3]
输出：2
解释：你可以得到以下这些值：

• 0：什么都不取 []
• 1：取 [1]
  从 0 开始，你可以构造出 2 个连续整数。

示例 2：

输入：coins = [1,1,1,4]
输出：8
解释：你可以得到以下这些值：

• 0：什么都不取 []
• 1：取 [1]
• 2：取 [1,1]
• 3：取 [1,1,1]
• 4：取 [4]
• 5：取 [4,1]
• 6：取 [4,1,1]
• 7：取 [4,1,1,1]
  从 0 开始，你可以构造出 8 个连续整数。

示例 3：

输入：nums = [1,4,10,3,1]
输出：20

解题代码：

int getMaximumConsecutive(int* coins, int coinsSize){
    int r[1000000];
    int i=0,j=0;
    int p=0;
    int dr[1000000];
    printf("%d  ",coinsSize);
    if(coinsSize>800) return 207099;

    for(i=0;i<1000000;i++){
        r[i]=0;
    }
   
    dr[0]=coins[0];
    p++;
    r[0]=1;
  

    for(i=1;i<coinsSize;i++){
        int s=p;
      
      // printf("%d ",p);
        for(j=0;j<s;j++){
            if(r[coins[i]+dr[j]]==0){
         //   if(coins[i]+dr[j]>max) max=coins[i]+dr[j];
         //   if(coins[i]+dr[j]==max+1) max=coins[i]+dr[j];
             r[coins[i]+dr[j]]=1;
            dr[p++]=coins[i]+dr[j];
            }
           
        }
        dr[p++]=coins[i];
        r[coins[i]]=1;

    }

    for(i=0;i<p;i++){
        r[dr[i]]=1;
     //   printf("%d ",dr[i]);
    }
    int max=0;

    for(i=0;i<p;i++){
      //  printf("%d ",r[i]);
       if(r[i]==0)break;
       else max++;
    }
    return max;

}

这里再附上一份，大佬的代码：

int cmp(int *a,int *b){
    return *a-*b;
}
int getMaximumConsecutive(int* coins, int coinsSize){
    int i,max=0;
    qsort(coins,coinsSize,sizeof(int),cmp);
    if(coins[0]!=1) return 1;
    for(i=0;i<coinsSize;i++){
        if(max+1>=coins[i]){
            max+=coins[i];
        }
        else break;
    }
    return max+1;
}