Link threads:vn.spoj.com/problems/LINEGAME/
Threads:
There is a rectangular band is divided into n squares numbered from left to right starting from 1. On the ith square one who recorded a positive integer, i = 1,2,…,n. At each turn, Participants may select an arbitrary number of cells on ice. Suppose that in order from left to right, players choose the cells i1, i2,…, I. Then that player scores achieved:

Request: Calculate the maximum possible number of points achieved from one plays.

Data:

• The first line contains integer n ( n ≤ 10⁶ ) the number of cells of the tape;
• The second line contains a positive integer n₁, the₂, …, the_n ( the_in ≤ 10⁴, i = 1, 2, …, n ) recorded on tape number. The consecutive number of the top row is separated by at least one space.

Result:

• A single number is the largest number of points can be achieved from one plays.

Example:

Ideas:(The idea of ​​nature refer, your code run only 80 point)

To be able to choose to be set so that the total effect of the greatest alternating as mentioned, we started all we will use the way to find the maximum points and minimum points, take maximum points total minus the sum of the minimum point is that the results need to find and keep in mind is not taking the minimum points at the beginning and end if (just to get the maximum severance). Specifically, as shown later:

#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>

#define INP "LINEGAME.INP"
#define OUT "LINEGAME.OUT"

using namespace std;

int main() {

	ifstream inp(INP);
	ofstream out(OUT);
	int n = 0;

	cin >> n;
	
	if (n==1){
		//cout << "n = 1";
		cin >> n;
		cout << n;
		return 0;
	}
	
	int* a = (int *) malloc(n * sizeof(int));
	//cout << n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		//cout << a[i] << " ";
	}
	//cout << endl;

	

	long sum = 0;
	int min = 0;
	
	for (int j = 0; j < n; j++) {
		// tim diem cuc dai
		if (j < n) {	
			sum -= min;	// tru di diem cuc tieu truoc do
//			cout << sum << " = " << "sum  - " << min << endl;
			while (j < n - 1 && a[j] < a[j + 1]) {
				j++;
			}
			sum += a[j]; // cong diem cuc dai vao
//			cout << sum << " = " << "sum  + " << a[j] << endl;
		}
		
		// tim diem cuc tieu, khong lay diem cuoi cung
		if (j < n - 1) {
			while (j < n - 1 && a[j] > a[j + 1]) {
				j++;
			}
			min = a[j]; // ghi lai de neu co cuc dai thi moi tru
		}
	}
	cout << sum <<endl;

	return 0;
}

Also you have to ask your references and have done 100 point, noi like this you still not understand:

Call d0[in] choosing a[in] or not and set trc plus call it the d1[in] k is selected or choose a[in] set it to minus
d1[in]:=max(d1[i-1],d0[i-1]-the[in]);
d0[in]:=max(d1[i-1]+the[in],d0[i-1]);