分割数组 给定一个大小为k的数组A，将其划分为两个连续子数组left和right

问题遇到的现象和发生背景

分割数组
描述

给定一个大小为k的数组A，将其划分为两个连续子数组left和right，使得：

（1） left中的每个元素都小于或等于right中的每个元素；

（2） left和right都是非空的；

（3） left 的长度要尽可能小。

在完成这样的分组后返回left的长度。可以保证存在这样的划分方法。

（1）可以保证至少有一种方法能够按题目所描述的那样对 A 进行划分。

（2）2 <= A.length <= 1000

（3） 0 <= A[i] <= 100

输入
5 5 0 3 8 6

解释：第一个值为k=5，其余值为数组A的值A= [5,0,3,8,6]

输出
3

解释：left = [5,0,3]，right = [8,6]

对于你这个问题可以参考如下链接：


你题目的解答代码如下：

#include <stdio.h>

int main()
{
    int i,k, resIndex=0;
    scanf("%d", &k);
    int A[k];
    for (i = 0; i < k; ++i)
        scanf("%d", &A[i]);
    int leftMaxVal = A[0], curMaxVal = A[0];//leftMaxVal记录A[0, resIndex]的最大值，curMaxVal记录A[0, i]的最大值
    for (i = 0; i < k; ++i){
        if (curMaxVal < A[i])
            curMaxVal = A[i];//更新A[0, i]的最大值
        if (A[i] < leftMaxVal){//在resIndex的右边出现A[i]比leftMaxVal小，说明resIndex不是第一个分割点
            resIndex = i;//分割点更新为i
            leftMaxVal = curMaxVal;//更新A[0, resIndex]的最大值为A[0, i]的最大值
        }
    }
    printf("%d\n", resIndex + 1);
    return 0;
}

img

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!

img