连续最大子数组和

一，一个记录当前子数组和，一个记录最大子数组和

 1 class Solution {
 2 public:
 3     int FindGreatestSumOfSubArray(vector<int> array) {
 6         int cur = array[0];
 7         int maxv=array[0];
 8         for (int i=1; i<array.size(); ++i) {
 9             if(cur<0) cur=array[i];
10             else cur+=array[i];
11             maxv=maxv>cur?maxv:cur;
12         }
13         return maxv;
14     }
15 };

二，返回最大子数组的序列，如果有多个最大子数组，返回最长的那个。时间复杂度O(n)，空间复杂度O(1) =>DP优化后就是滑动窗口的思想了

 1 class Solution {
 2 public:
 3     /**
 4      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 5      *
 6      * 
 7      * @param array int整型vector 
 8      * @return int整型vector
 9      */
10     vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
11         // write code here
12         int cur=array[0];
13         int maxv=array[0]; 
14         int lv=0,rv=0;  // 保存结果
15         int lv2=0,rv2=0;  // 滑动区间
16         for(int i=1;i<array.size();++i){
17             if(cur<0){
18                 cur=array[i];
19                 lv2=i;
20                 rv2=i;
21             }
22             else {
23                 cur+=array[i];
24                 rv2+=1;
25             }
26             if((maxv==cur && rv2-lv2>rv-lv) || maxv<cur){
27                 maxv=cur;
28                 rv=rv2;
29                 lv=lv2;
30             }
31         }
32         vector<int> res;
33         for(int j=lv;j<=rv;++j){
34             res.push_back(array[j]);
35         }
36         return res;
37     }
38 };

心之所愿，永不相忘

推荐这些技术文章：

最长连续不重复子序列

#include <iostream>using namespace std;const int N=10010;int a[N],s[N];int n;int main(){ cin>>n; int res=0; for(int i=0;i<n;i++) cin>>a[i]; for(int j=0,i=0;i<n;i++) { s[a[i]]...

最长连续不重复子序列_java

import java.util.*;

public class Main{
private static int N=100010;
private static int[] res=new int[N];
private static int[] temp=new int[N];

public static void main(String[] ...

2212. 射箭比赛中的最大得分 状态压缩

状态压缩
class Solution {
public:
vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
int msk = 0;
int maxScore = 0;

// i: 遍历2^12种结果
...

leetcode357 统计各位数字都不同的数字个数

思路：
排列组合。
实现：

1 class Solution {
2 public:
3 int A(int n,int m){
4 int res=1;
5 for(int i=1;i<=m;i++){
6 res*=n;
7 n--;
8 }
9 ...

回调函数（函数指针）的用法

#include <stdio.h>
typedef int(*callback)(int, int); //声明函数指针
typedef struct A
{
int a;
int b;
};
int add(int a, int b, callback p){
return (*p)(a, b);
}
int add(int a,...

2022-5-15 每日一题-leetcode

题目链接：https://leetcode.cn/problems/largest-triangle-area/
个人题解：暴力+叉积
代码：
class Solution {
public:
int cross(int x1,int y1,int x2,int y2){
return x1*y2-x2*y1;
}

int area(vector<...

vector<vector<int>>初始化

class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int n=mat.s...

【墨鳌】【面试题19. 正则表达式匹配】

class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();

auto matches = [&](int i, int j) {
if (i == 0) {
...

leetcode 785 染色法判断二分图

1 class Solution {
2 public:
3 bool isBipartite(vector<vector<int>>& graph) {
4 int n=graph.size();
5 vector<int>G[n],f(n,0);
6 for(int i=0;i&...

【墨鳌】【798. 得分最高的最小轮调】

class Solution {
public:
int bestRotation(vector<int>& A) {
int N = A.size();
vector<int> mark(N, 0);
for (int i = 0; i < N; ++i) {
int L = ...