1191. K 次串联后最大子数组之和-暴力动态规划，和优化算法

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，需要返回的 109 + 7 的 模 。

示例 1：

输入：arr = [1,2], k = 3
输出：9

示例 2：

输入：arr = [1,-2,1], k = 5
输出：2

示例 3：

输入：arr = [-1,-2], k = 7
输出：0
下面这个空间复杂度不能通过，

int kConcatenationMaxSum(int* arr, int arrSize, int k){
    long long  dp[k*arrSize+1];
    dp[0]=0;
    long long max=0;
    for(int i=1;i<k*arrSize+1;i++){
        if(dp[i-1]>0){
            dp[i]=(long long)fmax(0,dp[i-1]+arr[(i-1)%arrSize]);

        }
        else{
             dp[i]=(long long)fmax(arr[(i-1)%arrSize],0);

        }
        if(dp[i]>max){
            max=dp[i];
        }
    }
   
    printf("-- %d %d %d %d",dp[k*arrSize],dp[k*arrSize-1],dp[k*arrSize-2]);
    return max%1000000007;

}

优化之后的，即可通过，解题代码如下：

int kConcatenationMaxSum(int* arr, int arrSize, int k){
  
    long long max=0;
    int sum=0;
     for(int i=0;i<arrSize;i++){
         sum=sum+arr[i];
     }

    
     int i=1;
    int re=0;
     int backmax=0;
     int premax=0;
     
    if(k>=2){

            if(k>2&&sum>0){
                for(int i=0;i<k-2;i++)
                re=(sum+re)%1000000007;

            }
           
            
            int pre=0;
            for(int i=0;i<arrSize;i++){
               
                    pre=pre+arr[i];
            
                premax=(int)fmax(pre,premax)%1000000007;
               
            }
            int back=0;
           
            for(int i=arrSize-1;i>=0;i--){
               
                    back=back+arr[i];
              
                  backmax=(int)fmax(back,backmax)%1000000007;
               
            }

            re=re+backmax+premax;
              //printf("sbp %d %d %d",sum,back,back);
     }
   

     int  dp[arrSize+1];
        dp[0]=0;
     
        for(int i=1;i<arrSize+1;i++){
            if(dp[i-1]>0){
                dp[i]=(int)fmax(0,dp[i-1]+arr[(i-1)%arrSize]);

            }
            else{
                dp[i]=(int)fmax(arr[(i-1)%arrSize],0);

            }
            if(dp[i]>re){
                re=dp[i];
            }
        }
         
     
     
   // printf("-- %d %d %d %d",dp[k*arrSize],dp[k*arrSize-1],dp[k*arrSize-2]);
    return re%1000000007;

}