数据结构与算法分析学习笔记

//顺带锻炼一下结构体的基本操作
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INFTY -10000000;

//定义一个结构体
struct state{
  int left;
  int right;
  int sum;
};

//针对经过中点的的最长子数组
state Maxsoncrossarray(vector<int>& A, int l, int r, int mid){
    state ans;
    int max_left, max_right, left_sum, right_sum, sum;
    left_sum = INFTY;
    sum = 0;
    max_left = mid;
    for (int i = mid; i >= l; i--){
        sum += A[i];
        if(sum >= left_sum){
            left_sum = sum;
            max_left = i;
        }
    }
    max_right = mid + 1;
    right_sum = INFTY;
    sum = 0;
    for (int i = mid+1; i <= r; ++i){
        sum += A[i];
        if(sum >= right_sum){
            right_sum = sum;
            max_right = i;
        }
    }
    ans.left = max_left;
    ans.right = max_right;
    ans.sum = left_sum + right_sum;
    return ans;
}
state Maxsonarray(vector<int>& A, int l, int r){
    state ans, tmp1, tmp2, tmp3;
    //特殊情况，若只有一个元素
    if(l == r){
        ans.left = l;
        ans.right = r;
        ans.sum = A[l];
        return ans;
        
    }else{
        int mid = (l + r)/2;
        tmp1 = Maxsonarray(A, l, mid);
        tmp2 = Maxsonarray(A, mid+1, r);
        tmp3 = Maxsoncrossarray(A, l, r, mid);
    }
    if(tmp1.sum >= tmp2.sum && tmp1.sum > tmp3.sum) return tmp1;
    else if(tmp2.sum >= tmp1.sum && tmp2.sum > tmp3.sum) return tmp2;
    else return tmp3;
}

int main(){
    vector<int> A;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i){
        int tmp;
        scanf("%d", &tmp);
        A.push_back(tmp);
    }
    state ans = Maxsonarray(A, 0, n - 1);
    printf("%d\n%d\n%d", ans.left, ans.right, ans.sum);
    return 0;
}