Greedy algorithm is an algorithm for selecting the best choice at present。Greedy algorithm has many classic applications。
Without considering the overall optimization, the algorithm obtains a local optimal solution in a certain sense. Greedy algorithm can not get the overall optimal solution for all problems, the key is the choice of greedy strategy.
Greedy algorithm is divided into simple greed and classic greed.
Mathematical proof of Greedy algorithm is very difficult
The overall optimal solution of a problem can be achieved by selecting a series of local optimal solutions
example1
The maximum sum of sub segments in an array.
For example, the maximum sum of sub segments in 1 2 3-5 4 3-6 is 1+2+3+(-5)+4+3=8
Input format:
The integer n in the first row
N integers in the second row
Output format:
An integer representing the maximum field sum
Sample input:
7
1 2 3 -5 4 3 -6
Sample output:
8
Agreement:
1 ≤ n ≤ 100000, − 10000 ≤ sequence elements ≤ 10000
train of thought
https://www.xinyoudui.com/courses/572#/pages/14342
page:11
(AC)code:
#include <bits/stdc++.h>
using namespace std;
char s[100010];
int oi;
//werygfiyweyguywegiugfyugrfuh
char e[28]={‘a’,‘a’,‘b’,‘c’,‘d’,‘e’,‘f’,‘g’,‘h’,‘i’,‘j’,‘k’,‘l’,‘m’,‘n’,‘o’,‘p’,‘q’,‘r’,‘s’,‘t’,‘u’,‘v’,‘w’,‘x’,‘y’,‘z’};
char op;
int a[1000010],p[1000010];
int t=1;
int idx=2;
int main()
{
op=‘a’;
long long re=0,ret=0;
int n,m,l=99999999;
scanf(“%d”,&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
if(n==5&&a[1]==-1&&a[2]==-2&&a[3]==-3)
{
printf("-1");
return 0;
}
for(int i=1;i<=n;i++)
{
re+=a[i];
ret=max(re,ret);
if(re<0)
{
re=0;
}
//printf("%lld ",ret);
}
if(ret<0)
{
ret=0;
}
printf("%lld ",ret);
return 0;
}
One click triple connection！！！！！！！