删除子数组的最大得分

删除子数组的最大得分

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],…,a[r] ，那么它就是 a 的一个子数组。

示例 1：

输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]

示例 2：

输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]
这题其实有技巧，因为给的数不大，所以很方便通过空间复杂度去优化该算法

int maximumUniqueSubarray(int* nums, int numsSize){
    int r[100000];
    int first=0,end=0;
    int i;
    int po=0;
    int len=0;
    int j;
    int max[numsSize];
    int n=0;
    for(i=0;i<numsSize;i++){
        max[i]=0;
    }

    for(i=0;i<numsSize;i++){
        int num=nums[i];
        int sum=0;
        for(j=po;j<len;j++){
            sum=sum+r[j];
         if(num==r[j]){
             n++;
            int k;
             max[n]=max[n-1]-sum;
            
             po=j+1;
             i=i-1;
             break;
         }
        }
        if(j==len){
            max[n]=max[n]+num;
            r[len++]=num;
        }
        
    }
    int pm=0;
      for(i=0;i<numsSize;i++){
          if(pm<max[i]){;
              pm=max[i];
          }
       printf("%d ",max[i]);
    }

return pm;
}

下面是用滑动窗口去去解决问题，这很方便：

#define MAX_SIZE 10001
int maximumUniqueSubarray(int* nums, int numsSize){
    int freq[MAX_SIZE] = {0};
    int sum = 0;
    int ans = 0;
    int left = 0;
    int right = 0;

    while (right < numsSize) {
        sum += nums[right];
        freq[nums[right]]++;

        while (freq[nums[right]] > 1) {
            sum -= nums[left];
            freq[nums[left]]--;
            left++;
        }
        ans = fmax(ans, sum);
        right++;
    }
    return ans;
}