例题，最大子段和

Given an array of n numbers, our task is to calculate the maximum subarray sum. from《编程珠玑》

//举例
-1  2  4  -3  5  2  -5  2
//最大子段和是10
    2  4  -3  5  2

算法1，O(n^3)

int best = 0;
for (int a = 0; a < n; a++) {
    for (int b = a; b < n; b++) {
       int sum = 0;
       for (int k = a; k <= b; k++) {
           sum += array[k];
        }
       best = max(best,sum);
    }
}
cout << best << "\n";

算法2，O(n^2)

int best = 0;
for (int a = 0; a < n; a++) {
    int sum = 0;
    for (int b = a; b < n; b++) {
       sum += array[b];
       best = max(best,sum);
    }
}
cout << best << "\n";

算法3，O(n)

Consider the subproblem of finding the maximum-sum subarray that ends at position k. There are two possibilities:

1. The subarray only contains the element at position k.
2. The subarray consists of a subarray that ends at position k − 1,
followed by the element at position k.

In the latter case, since we want to find a subarray with maximum sum, the subarray that ends at position k − 1 should also have the maximum sum. Thus, we can solve the problem efficiently by calculating the maximum subarray sum for each ending position from left to right.

int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
    sum = max(array[k],sum+array[k]);
    best = max(best,sum);
}
cout << best << "\n";

aha，这是就是动态规划..

所以，你会了一个经典dp问题 当有人把动态规划认为是学习算法的里程碑，或者分水岭，此时，你已经悄然渡过

// 另外一种，最大字段和的写法
#include <bits/stdc++.h>
using namespace std;
int a[20], n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int maxn = -0x3f3f3f3f, area = 0;
    for (int i = 1; i <= n; i++){
        area += a[i];
        if (area > maxn) maxn = area;
        if (area < 0) area = 0;  //另起炉灶
    }
    cout << maxn << '\n';
    return 0;
}
=================
#include <bits/stdc++.h>
using namespace std;
int a[20], n;
int dp[20];
int maxn = -0x3f3f3f3f;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++){
        dp[i] = max(dp[i - 1], 0) + a[i];     //另起炉灶
        maxn = max(maxn, dp[i]);    
    }
    cout << maxn << '\n';
    return 0;
}