子数组相加和为母数组的和的一半（动态规划题目）

bool IsMagical(vector<int>& vec)
{
    int len = vec.size();
    int sum = accumulate(vec.begin(), vec.end(), 0);
    if (sum & 1)
        return false;

    int mid = (sum>>1);
    vector<int> dp(mid + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < len; ++i)
    {
        for (int j = mid; j > 0; --j)
        {
            if (j >= vec[i])
                dp[j] = max(dp[j], dp[j - vec[i]]);
        }
    }
    if (dp[mid])
        return true;
    else
        return false;
}

解题思路：vec是一个数组（已经升序排序），求vec的子数组的相加和为vec的相加和一半的结果，返回值是一个bool类型。