题解 | #跳台阶扩展问题#

解法一，动态规划解决

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
int num[100000] = {0};
class Solution {
public:
    int FindGreatestSumOfSubArray(ListNode* head) {
        int n,i = 0;
        while(head != NULL){
            num[i++] = head->val;
            head = head->next;
        }
        n = i;
        long int MAX = num[0],sum = num[0];
        for (int i = 1; i < n; ++i) {
            if (sum < 0 && sum < num[i])
                sum = num[i];
            else
                sum += num[i];
            MAX = max(MAX, sum);
        }
        return MAX;
    }
};

解法二，递归解决，后面补充