【动态规划】【前缀和】【和式变换】100216. K 个不相交子数组的最大能量值

class Solution {
public:
  long long maximumStrength(vector<int>& nums, int k) {
    m_c = nums.size();
    vector<long long> pre(m_c+1);
    for (int iK = 0; iK < k; iK++)
    {
      vector<long long> dp(m_c + 1, -1E14);
      if (1 & iK)
      {
        Odd(dp, pre, nums,k-iK);
      }
      else
      {
        Even(dp, pre, nums, k - iK);
      }
      pre.swap(dp);
    }
    return *std::max_element(pre.begin(), pre.end());
  }
  void Odd(vector<long long>& dp, const vector<long long>& pre,const vector<int>& nums,const int x )
  {//奇数
    long long maxPre = -1E14,llMax = -1E14,llSum=0;
    for (int j = 1; j <= m_c ; j++)
    {//假定第iK个子数组是nums[i,j]，则最大值为：maxPre - sum[0...j] + sum[0...i)，llMax=第一项和第三项合并
      maxPre = max(maxPre, pre[j-1]);
      llMax = max(llMax, maxPre + llSum);//第iK个子数组，以nums[j]开头     
      llSum += (long long)nums[j-1]*x;
      dp[j] = llMax - llSum;      
    }
  }
  void Even(vector<long long>& dp, const vector<long long>& pre, const vector<int>& nums, const int x)
  {//偶数
    long long maxPre = (long long)-1E14, llMax = -1E14, llSum = 0;
    for (int j = 1; j <= m_c; j++)
    {//假定第iK个子数组是nums[i,j]，则最大值为：maxPre + sum[0...j] - sum[0...i)，llMax=第一项和第三项合并
      maxPre = max(maxPre, pre[j-1]);
      llMax = max(llMax, maxPre - llSum);//第iK个子数组，以nums[j]开头     
      llSum += (long long)nums[j - 1] * x;
      dp[j] = llMax + llSum;      
    }
  }
  int m_c;
};

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  vect
  or<int> nums;
  int k;
  {
    Solution sln;
    nums = { -100000000, -10000000, 123, 234 }, k = 3;
    auto res = sln.maximumStrength(nums, k);
    Assert(-30000012, res);
  }
  {
    Solution sln;
    nums = { 1,2,3,-1,2 }, k = 3;
    auto res = sln.maximumStrength(nums, k);
    Assert(22, res);
  }
  {
    Solution sln;
    nums = { 12,-2,-2,-2,-2 }, k = 5;
    auto res = sln.maximumStrength(nums, k);
    Assert(64, res);
  }
  {
    Solution sln;
    nums = { -1,-2,-3 }, k = 1;
    auto res = sln.maximumStrength(nums, k);
    Assert(-1, res);
  }
}

class Solution {
public:
  long long maximumStrength(vector<int>& nums, int k) {
    m_c = nums.size();
    vector<long long> pre(m_c + 1);
    for (int iK = 0; iK < k; iK++)
    {
      vector<long long> dp(m_c + 1, -1E14);
      long long maxAdd = -1E14, maxSub = -1E14,maxPre = -1E14;
      long long llSum = 0;
      for (int j = 1; j <= m_c; j++)
      {
        maxPre = max(maxPre, pre[j-1]);
        maxAdd = max(maxAdd, maxPre - llSum);
        maxSub = max(maxSub, maxPre + llSum);
        llSum += nums[j - 1]*(long long) ( k - iK );
        dp[j] = (iK & 1) ? (maxSub - llSum) : (maxAdd + llSum);
      }
      pre.swap(dp);
    }
    return *std::max_element(pre.begin(), pre.end());
  }
  int m_c;
};