//
// Created by ayonel on 2016/12/27.
//

/**
 * 如果两个字符串中的字符一样，出现次数也一样，只是出现的顺序的顺序不一样，则认为这两个字符串是兄弟字符串。
 * 例如"bad"和"adb"即为兄弟字符串。现提供一个字符串，请问如何在字典中迅速找到它的兄弟字符串
 *
 * 例如待查找的字符串是"apple",字典是{"appl","paal","aplep","bb","leapp","hello"}
 * 则输出的单词应为："aplep", "leapp"
 *
 * 首先用快排对整个字典排序，排序的比较标准是每个单词内部先排好序之后的签名，比如"apple"--->"aelpp","dddap"--->"adddp";
 * 再用排序之后的字典二分搜索目标单词，找到签名一样的单词，则分别向上，向下找同样签名的单词，并输出；
 * */

#include <stdio.h>
#include <string.h>
#define MAX_LEN 20 // 假定每个单词的最大字符数是20
#define WORD_COUNT 6
char set[][WORD_COUNT] = {"appl","paal","aplep","bb","leapp","hello"};


// 通过对单词插入排序，获取签名，不要直接传入原数组中的单词，应该传入单词的副本，反正覆盖原数组
char* sign(char *result) {
    int j = 0;
    int i = 1;
    char tmp = ' ';
    //插入排序
    while (result[i] != '\0') {
        tmp = result[i];
        for(j = i; j > 0 && result[j-1] > tmp; j--) {
            result[j] = result[j-1];
        }
        result[j] = tmp;
        i++;
    }
    return result;
}

//比较两个单词的签名大小
int compare_by_sign(char *a, char *b) {
    char sort_a[MAX_LEN];
    char sort_b[MAX_LEN];
    strcpy(sort_a, a);
    strcpy(sort_b, b);

    return strcmp(sign(sort_a), sign(sort_b));
}

//比较两个单词大小
int compare(char *a, char *b) {
    return strcmp(a, b);
}

//交换原数组中下标为i和j的单词位置
void swap(int i, int j){
    if (i == j)
        return;
    char tmp[MAX_LEN];
    strcpy(tmp, set[i]);
    strcpy(set[i], set[j]);
    strcpy(set[j], tmp);
}

// 对原数组按照签名大小，进行快排
void qsort(int l, int u) {
    if (l > u)
        return;
    int m = l;

    for(int i = l+1; i <= u; i++) {
        if(compare_by_sign(set[i], set[l]) < 0){
            swap(i,++m);
        }
    }
    swap(m,l);

    qsort(l, m-1);
    qsort(m+1, u);
}

//在排序好的数组中二分查找签名相同的单词，并输出
void bsearch(int l, int u, char *word_sign, int *is_found) {
    int mid = (u - l) / 2;
    if (l > u) {
        return;
    }
    char mid_sign[MAX_LEN];
    strcpy(mid_sign, set[mid]);
    sign(mid_sign);
    int com_result = compare(mid_sign, word_sign);
    if (com_result > 0)
        bsearch(l, mid-1, word_sign, is_found);
    if (com_result < 0)
        bsearch(mid+1, u, word_sign, is_found);
    if (com_result == 0){
        //找到了，开始向下以及向上寻找相同签名的词
        int flag = mid;
        printf("found brother word:\n%s\n",set[mid]);
        *is_found = 1;
        mid--;
        flag++;
        //向上找
        while(mid > 0){
            if(compare(sign(set[mid]), word_sign) == 0)
                printf("%s\n",set[mid]);
            else
                break;
            mid--;
        }
        //向下找
        while(flag < WORD_COUNT) {
            if(compare(sign(set[flag]), word_sign) == 0)
                printf("%s\n",set[flag]);
            else
                break;
            flag++;
        }
    }
}

int main() {
    qsort(0, WORD_COUNT-1); //对原数组排序
    char des[] = "apple"; //待查找单词
    char *word_sign;
    word_sign = sign(des); //待查找单词的签名
    printf("sign is: %s\n", word_sign);

    int is_found = 0; //标记是否找到
    bsearch(0, WORD_COUNT, sign(des), &is_found); //二分查找
    if (is_found == 0) { //未找到
        printf("%s\n", "can not found brother word!!");
    }
}

#include <stdlib.h>
int x[10] = {31,-41,59,26,-53,58,97,-93,-23,84};
float max(float x, float y) {
    return x >= y? x : y;
}

float max3(float x, float y, float z) {
    int larger = max(x, y);
    return max(larger, z);
}
//核心算法
float maxsum3(int l, int u) {
    if (l > u)
        return 0;
    if (l == u)
        return max(0, x[1]);
    int m = (l + u) / 2;
    //找出以m为起点的向左的最大子向量
    float lmax  = 0;
    float sum = 0;
    for (int i = m; i >= 1; i--) {
        sum += x[i];
        lmax = max(lmax, sum);
    }
    //找出以m为起点的向右的最大子向量
    float rmax = 0;
    sum = 0;
    for(int i = m + 1; i < u; i++) {
        sum += x[i];
        rmax = max(rmax, sum);
    }
    //lmax+rmax 就是经过m的最大子向量
    return max3(lmax+rmax, maxsum3(l, m), maxsum3(m+1, u));
}
int main(){
    printf("%f", maxsum3_l(0,9));
}

#include <stdlib.h>
int x[10] = {31,-41,59,26,-53,58,97,-93,-23,84};
float maxsum4(int n){
    float maxsofar = 0;
    float maxendinghere = 0;
    for (int i = 0; i < n; ++i) {
        maxendinghere = max(maxendinghere+x[i], 0);
        maxsofar = max(maxsofar, maxendinghere);
    }
    return maxsofar;
}

int main(){
    printf("%f", maxsum4(10));

}

#include <stdlib.h>
int x[10] = {31,-41,59,26,-53,58,97,-93,-23,84};
float max(float x, float y) {
    return x >= y? x : y;
}

float max3(float x, float y, float z) {
    int larger = max(x, y);
    return max(larger, z);
}
float maxsum3_l(int l, int u) {
    if (l > u)
        return 0;
    if (l == u)
        return max(0, x[l]);
    int m = (l + u) / 2;

    float lmax  = 0;
    float sum = 0;
    int last_l = m;  //向左找时最大子向量的结束位置
    for (int i = m; i >= 0; i--) {
        sum += x[i];
        if (lmax<=sum) {
            lmax = sum;
            last_l--;
        }
    }

    int last_r = m+1; //向右找时最大子向量的结束位置
    float rmax = 0;
    sum = 0;
    for(int i = m + 1; i <= u; i++) {
        sum += x[i];
        if (rmax<sum) {
            rmax = sum;
            last_r++;
        }
    }
    return max3(lmax+rmax, maxsum3_l(l, last_l-1), maxsum3_l(last_r, u)); //直接从结束位置向左及向右找
}
int main(){
    printf("%f", maxsum3_l(0,9));
}